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;
}