本文共 3906 字，大约阅读时间需要 13 分钟。
题目如下：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.
即从s中找出所有索引，这些索引都是words中所有word连接组成的字符串在s中的位置，每个word必须且只能出现一次。
转自
这道题看似比较复杂，其实思路和差不多。因为那些单词是定长的，所以本质上和单一个字符一样。和的区别只在于我们需要维护一个字典，然后保证目前的串包含字典里面的单词有且仅有一次。思路仍然是维护一个窗口，如果当前单词在字典中，则继续移动窗口右端，否则窗口左端可以跳到字符串下一个单词了。假设源字符串的长度为n，字典中单词的长度为l。因为不是一个字符，所以我们需要对源字符串所有长度为l的子串进行判断。做法是i从0到l-1个字符开始，得到开始index分别为i, i+l, i+2*l, ...的长度为l的单词。这样就可以保证判断到所有的满足条件的串。因为每次扫描的时间复杂度是O(2*n/l)(每个单词不会被访问多于两次，一次是窗口右端，一次是窗口左端)，总共扫描l次（i=0, ..., l-1)，所以总复杂度是O(2*n/l*l)=O(n)，是一个线性算法。空间复杂度是字典的大小，即O(m*l)，其中m是字典的单词数量。代码如下：
public ArrayList findSubstring(String S, String[] L) { // Note: The Solution object is instantiated only once and is reused by each test case. ArrayList res = new ArrayList (); if(S==null || S.length()==0 || L==null || L.length==0) return res; HashMap map = new HashMap (); for(int i=0;i curMap = new HashMap (); int count = 0; int left = i; for(int j=i;j<=S.length()-L[0].length();j+=L[0].length()) { String str = S.substring(j,j+L[0].length()); if(map.containsKey(str)) { if(curMap.containsKey(str)) curMap.put(str,curMap.get(str)+1); else curMap.put(str,1); if(curMap.get(str)<=map.get(str)) count++; else { while(curMap.get(str)>map.get(str)) { String temp = S.substring(left,left+L[0].length()); if(curMap.containsKey(temp)) { curMap.put(temp,curMap.get(temp)-1); if(curMap.get(temp)
附上python代码：
class Solution(object): def findSubstring(self, s, words): """ :type s: str :type words: List[str] :rtype: List[int] """ result = [] if s == None or words == None: return result len_s = len(s) len_words = len(words) if len_s == 0 or len_words == 0: return result len_word = len(words[0]) dict = {} self.produceDict(words, dict) for i in range(len_word): left = i j = i count = 0 curDict = {} for j in range(i, len_s - len_word + 1, len_word): str = s[j:j+len_word] if dict.get(str, None) == None: curDict.clear() count = 0 left = j + len_word else: count_str = curDict.setdefault(str, 0) count_str += 1 curDict[str] = count_str if curDict[str] <= dict[str]: count += 1 else: while curDict[str] > dict[str]: temp = s[left:left + len_word] temp_count = curDict.get(temp, 0) if temp_count != 0: curDict[temp] -= 1 if curDict[temp] < dict[temp]: count -= 1 left += len_word if count == len_words: result.append(left) temp = s[left:left + len_word] count_temp = curDict.get(temp, 0) if count_temp != 0: curDict[temp] -= 1 count -= 1 left = left + len_word return result def produceDict(self, words, dict): for i in range(len(words)): count = dict.setdefault(words[i], 0) count += 1 dict[words[i]] = count 转载地址：http://ymbvb.baihongyu.com/