题目：
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) in s that is a concatenation of each word in wordsexactly once and without any intervening characters.
For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]
You should return the indices: [0,9].
题意：题意很重要，开始理解错了，以为要求的是words中每个单词出现的index，真正的题意是，words中每一个单词都出现一次，并且中间不夹杂着其他的单词，即word中所有字符串组成的所有可能在s中出现的index。
思路：建立一个map来维护words的内容，key为words的string，value为对应的数量。 由于words的单词长度相同，因此每次查找的窗口大小一致，为words所有单词的总长度，不用判断边界条件。在判断过程中，建立一个临时的map，来与初始的map进行比较，符合的时候，向list中加入此时的index
代码：
public class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> list = new ArrayList<Integer>(); if(s == null || s.length() == 0 || words.length == 0) return list; int wordCount = words.length; int wordlen = words[0].length(); int len = wordlen * wordCount; //总长度 Map<String, Integer> map = new HashMap<String, Integer>(); Map<String, Integer> cur = new HashMap<String, Integer>(); for(int i = 0 ; i < wordCount ; i++){ if(!map.containsKey(words[i])) map.put(words[i], 1); else map.put(words[i], map.get(words[i])+1); } boolean flag = true; //标志位 for(int i = 0 ; i < s.length() - len + 1 ; i++){ cur.clear(); //循环开始的时候清空上一次的操作 flag = true; for(int j = 0 ; j < wordCount ; j++){ String temp = s.substring(i + j*wordlen, i + wordlen*(j+1)); //每一个窗口 if(!map.containsKey(temp)){ flag = false; break; } if(!cur.containsKey(temp)) cur.put(temp, 1); else cur.put(temp, cur.get(temp)+1); if(cur.get(temp) > map.get(temp)){ flag = false; break; } } if(flag) // 如果不是意外break 则内容相符 list.add(i); } return list; } }
上面的是自己的思路，不是最快速的，大概是700ms 下面将内外循环换一下 速度提升了一倍 300ms
代码：
public class Solution { public static ArrayList<Integer> findSubstring(String S, String[] L) { ArrayList<Integer> res = new ArrayList<Integer>(); if(S==null||L==null||S.length()==0||L.length==0) return res; int wordLen = L[0].length();//same length for each word in dictionary //put given dictionary into hashmap with each word's count HashMap<String, Integer> dict = new HashMap<String, Integer>(); for(String word: L){ if(!dict.containsKey(word)) dict.put(word, 1); else dict.put(word, dict.get(word) + 1); } for(int i = 0; i < wordLen; i++){ int count = 0; int index = i;//index of each startpoint HashMap<String, Integer> curdict = new HashMap<String, Integer>(); //till the first letter of last word for(int j = i; j <= S.length() - wordLen; j += wordLen){ String curWord = S.substring(j, j + wordLen); //check each word to tell if it existes in give dictionary if(!dict.containsKey(curWord)){ curdict.clear(); count = 0; index = j + wordLen; }else{ //form current dictionary if(!curdict.containsKey(curWord)) curdict.put(curWord, 1); else curdict.put(curWord, curdict.get(curWord) + 1); //count for current found word and check if it exceed given word count if(curdict.get(curWord) <= dict.get(curWord)){ count++; }else{ while(curdict.get(curWord) > dict.get(curWord)){ String temp = S.substring(index, index + wordLen); curdict.put(temp, curdict.get(temp)-1); if(curdict.get(temp)<dict.get(temp)){ count--; } index = index + wordLen; } } //put into res and move index point to nextword //and update current dictionary as well as count num if(count == L.length){ res.add(index); String temp = S.substring(index, index + wordLen); curdict.put(temp, curdict.get(temp)-1); index = index + wordLen; count--; } } }//end for j }//end for i return res; } }
最后自己增加了一些改进 简化了一下代码：
public class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> list = new ArrayList<Integer>(); if(s == null || words == null || s.length() == 0) return list; int l = words[0].length(); int n = words.length; int len = l*n; Map<String, Integer> map = new HashMap<String, Integer>(); for(int i = 0 ; i < words.length ; i++) { if(map.containsKey(words[i])) { map.put(words[i], map.get(words[i]) + 1); }else map.put(words[i], 1); } for(int i = 0 ; i < l ; i++) { int index = i; //如果成功的返回值 int count = 0; //匹配成功的个数 Map<String, Integer> tempMap = new HashMap<String, Integer>(); for(int j = i ; j <= s.length() - l ; j += l) { // 一定要有等号 String str = s.substring(j, j + l); //每一个切分 if(!map.containsKey(str)) { // 整体右移 tempMap.clear(); count = 0; index = j + l; }else { if(!tempMap.containsKey(str)) { tempMap.put(str, 1); }else { tempMap.put(str, tempMap.get(str) + 1); } while(tempMap.get(str) > map.get(str)) { // 循环右移 知道去除最远的相同字符串 String left = s.substring(index, index + l); // 窗口最右边的str tempMap.put(left, tempMap.get(left) - 1); // 更新 index += l; // 右移 count--; // 减少一个匹配值 } count++; // 成功匹配到一个 if(count == n) { // 全部匹配成功 list.add(index); } } } // end of for j } return list; } }
参考链接：http://www.cnblogs.com/springfor/p/3872516.html