[LeetCode]Substring with Concatenation of All Words

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).

思路：利用两个数据结构toFind ,hasFound分别表示需要找的字符串和已经查找到的字符串然后遍历s,如果能够按 words[0].length为步长查找 words.length 步满足 toFind 和 hasFound 一致的话则表示查找到一个满足的组合代码： public List<Integer> findSubstring(String s, String[] words) {List<Integer> rs = new LinkedList<Integer>();Map<String, Integer> toFind = new HashMap<String, Integer>();Map<String, Integer> hasFound = new HashMap<String, Integer>();for (int i = 0; i< words.length; ++i){//去重if(toFind.get(words[i]) == null){toFind.put(words[i], 1);}else {toFind.put(words[i], toFind.get(words[i]) + 1);}}int wordsCount = words.length;int step = words[0].length();int loop = s.length() – wordsCount * step;//循环查找的次数for(int i = 0; i <= loop; ++ i){//外层循环保遍历所有可能的顺序字符串hasFound.clear();int j =0;for(; j < wordsCount; ++j){int k = i + j * step;//以step为单元String sub = s.substring(k, k + step);if(! toFind.containsKey(sub)) break;if(hasFound.containsKey(sub)){hasFound.put(sub, hasFound.get(sub) + 1);}else {hasFound.put(sub, 1);}if(hasFound.get(sub) > toFind.get(sub)) break;}if(j == wordsCount) rs.add(i);}return rs;}

，每个人都有自己鲜明的主张和个性，