You are given a string,s, and a list of words,words, that are all of the same length. Find all starting indices of substring(s) insthat is a concatenation of each word inwordsexactly once and without any intervening characters.

For example, given:
s:"barfoothefoobarman"
words:["foo", "bar"]

You should return the indices:[0,9].
(order does not matter).

Solution: i从[0, s.length() - m * n]遍历,每个i取substring [i + j * n, i + (j + 1) * n], j∈[0, m),看是否与词典相同

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<Integer>();
        if(s == null || s.length() == 0 || words == null || words.length == 0){
            return ans;
        }
        int m = words.length, n = words[0].length();
        HashMap<String, Integer> dict = new HashMap<String, Integer>();
        HashMap<String, Integer> found = new HashMap<String, Integer>();
        for(String word : words){
            dict.put(word, dict.containsKey(word) ? dict.get(word) + 1 : 1);
        }
        for(int i = 0; i <= s.length() - m * n; i++){
            int j;
            for(j = 0; j < m; j++){
                int k = i + j * n;
                String string = s.substring(k, k + n);
                if(!dict.containsKey(string)){
                    break;
                }
                found.put(string, found.containsKey(string) ? found.get(string) + 1 : 1);
                if(found.get(string) > dict.get(string)){
                    break;
                }
            }
            if(j == m){
                ans.add(i);
            }    
            found.clear();
        }
        return ans;
    }

results matching ""

    No results matching ""