题目描述

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

来源：此题在力扣中国的链接

解题原理

正式开始之前，再次呼吁：检查空输入。

算法原型

我们先对着样例思考一下如何解决这道题：

输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]

---

1. 不谈动规，那么必然是要用循环遍历整个字串。
2. 考虑到单词的长度是相同的，我们可以记录下单词的长度wlen，然后在循环检测的过程中，我们可以让步长直接为wlen。

wlen == 3

in loop k:
...foobar...
   ↑

in loop k + 1
...foobar...
      ↑

3. 为了记录当前到底检测通过了几个词，我们可以设置一个计数器，记录已经记录了多少个词。如果计数器等于words的长度，那么就证明我们已经完成了目标

words = ['bar', 'foo']
#wordsLen == 2
counter = 0

in loop 0:
barfoo...
↑
counter == 1

in loop 1:
barfoo
   ↑
counter == 2 == wordsLen

此时counter == wordsLen，因此ans里面就增加一个0。

4. 如果我们遇到了词表外的单词，比如the，那么我们就continue，跳过这个词。同时，由于这个间隔的存在，我们需要清空counter。

基于上面这个思想，我们可以写出以下伪代码：

for i in range(0, stringLen, wlen):
    if s.getword(i) in words:
        counter += 1
        if counter == wordsLen: 
            ans.append(substrHead(i)) 
            counter = 0
    else:
        counter = 0

return ans

然后我们着手优化这个原型。

优化1：words有重复词

原题的样例2就已经告诉我们，words内是可以重复的：

输入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出：[]

那么该如何处理这个问题？我们可以考虑把计数器counter改成一个字典，记录下已经记录过了什么词，以及记录过了多少词。

#设置比较对象
allwords = {}
for w in words:
    allwords[w] = allwords.get(w, 0) + 1
counter = {}

...in loop:
word = s.getword(i)
if word in words:
    counter[word] += 1
if counter == allwords:
    ans.append(substrHead(i))
    counter = {}

应当指出，从这里开始，substrHead是通过计算counter所记录词的个数，计算字串开头在哪里。这对之后的优化非常有帮助。

foobarbarthe
         ↑
         i
对于不同的counter：
{'bar': 2, 'foo': 1} - substrHead(i) == 0
{'bar': 2, 'foo': 0} - substrHead(i) == 3

优化2：考虑词数过多

样例2中有这么一段：

wordgoodgoodgood...

显然，这里有太多good了。正好，我们在上面已经设置了一个字典，只要判断一下是否超过allwords里面的数字就行。

if word in words:
    if counter.get(word, 0) + 1 > allwords[word]:
        counter = {}
        counter[word] = 1
    else:
        counter[word] = counter.get(word, 0) + 1

重要优化1：考虑重叠的可行解

在样例1中，可行解是这样的：

[barfoo]the[foobar]man

然而，如果我们输入：

'barfoothebarfoo'
['bar', 'foo', 'the']

你会发现，我们算法只能发现下面的可行解：

[barfoothe]barfoo

因为我们在检测之后，就跳过了之前的全部字串！然而，真实的可行解是这样的：

[barfoothe]barfoo
bar[foothebar]foo
barfoo[thebarfoo]

为了解决这个问题，我们可以做出进一步的改进。

需要用暴力的方法去一个一个鉴别吗？那么我们就浪费了很多中间已经检测成立的信息。所以，我们可以将检测区域想象一个滑动的区域，在一个可行解成立的时候，我们只需要把字串头前移wlen即可。

比如，对于这个可行解：

[barfoothe]barfoo
counter = {'bar': 1, 'foo': 1, 'the': 1}

我们只需要将它变成：

bar[foothe]barfoo
counter = {'bar': 0, 'foo': 1, 'the': 1}

然后接着检测就可以了！下面就是对代码的修改：

if counter == allwords:
    ans.append(substrHead(i))
    counter[s.getword(substrHead(i))] -= 1

优化3：可行解与冗余词的重叠

再看样例2。重复的单词，如果不是word，而是good，那么会发生什么呢？

在目前的算法下，会出现这样的情况：

[wordgoodgood]goodbestword
              ↑

词数过多，我们清空了counter，然后发现，剩下的goodbestword组不成可行解。

但是，我们自己看，是能看到可行解在哪里的：

wordgood[goodgoodbestword]

利用我们刚才滑动区域的思想，其实也可以解决这个问题。当词数超出限制，将字串头移动到词数符合限制为止即可。

if counter[word] + 1 > allwords[word]:
    while substrHead(i) != i and counter[word] + 1 > allwords[word]:
        counter[s.getword(substrHead(i))] -= 1
    counter[word] += 1

[wordgoodgood]goodbestword
              ↑
word[goodgood]goodbestword
              ↑
wordgood[good]goodbestword
              ↑
wordgood[goodgood]bestword
             ↑
wordgood[goodgood]bestword
                  ↑

重要优化2：不定长的表外词

其实我们刚才的讨论都基于一个假设：表外单词是定长的，和表内单词长度相同。但是，题目只提出了表内单词同长，并没有提出表外单词同长。所以，该怎么解决像这样的问题呢：

输入：
s = "barfoothetafoobar",
words = ["foo","bar"]

我们已经做了这么多优化了，难道前功尽弃，重归暴力吗？当然不行，记住，要充分利用花了时间处理过的信息。

我们刚才的算法处理了什么东西？是步长为wlen的条件下，整个字符串的可行解。

重点是，如果求过了s的可行解，再去求s[wlen:]的可行解，有什么区别？除了0，两组可行解没有区别！

这就意味着，我们不需要将从头到尾遍历字符串，作为算法的开头，而是只需要遍历s[:wlen]就可以了！

例如，当遍历计数器j == 0时：

[bar][foo][the][taf][oob]ar
^^^^^^^^^^ 

而当j == 2时：

ba[rfo][oth][eta][foo][bar]
                 ^^^^^^^^^^ 

据此修改的代码如下：

for j in range(wlen):
    i = j
    while i + wlen < slen:
        ...
        i += wlen
return ans

最终代码

经过以上针对原型的优化，相信你也可以自己写出这题的正确代码了。这里提供一份LeetCode提供的50ms左右的样例：

class Solution:
    def findSubstring(self, s: 'str', words: 'List[str]') -> 'List[int]':
        if not s or words==[]:
            return []
        lenstr=len(s)
        lenword=len(words[0])
        lensubstr=len(words)*lenword
        times={}
        for word in words:
            if word in times:
                times[word]+=1
            else:
                times[word]=1
        ans=[]
        for i in range(min(lenword,lenstr-lensubstr+1)):
            self.findAnswer(i,lenstr,lenword,lensubstr,s,times,ans)
        return ans
    def findAnswer(self,strstart,lenstr,lenword,lensubstr,s,times,ans):
        wordstart=strstart
        curr={}
        while strstart+lensubstr<=lenstr:
            word=s[wordstart:wordstart+lenword]
            wordstart+=lenword
            if word not in times:
                strstart=wordstart
                curr.clear()
            else:
                if word in curr:
                    curr[word]+=1
                else:
                    curr[word]=1
                while curr[word]>times[word]:
                    curr[s[strstart:strstart+lenword]]-=1
                    strstart+=lenword
                if wordstart-strstart==lensubstr:
                    ans.append(strstart)

这里还提供了一个小优化：for i in range(min(lenword,lenstr-lensubstr+1)):，对应我们刚才说的，就是单词较长的时候，我们可以只需要遍历到最终字串的长度已经触及字符串总长度的时候停下来：

"aaaaabbbbbcccccdd"
['aaaaa','bbbbb','ccccc']
lenword == wlen == 5
lenstr - lensubstr + 1 == slen - wlen * words + 1 == 3
取后者即可。

感谢阅读！