題目描述
給定一個字符串 s 和一些長度相同的單詞 words蓬衡。找出 s 中恰好可以由 words 中所有單詞串聯(lián)形成的子串的起始位置碎捺。
注意子串要與 words 中的單詞完全匹配，中間不能有其他字符惨篱，但不需要考慮 words 中單詞串聯(lián)的順序盏筐。
來源：此題在力扣中國的鏈接
解題原理
正式開始之前，再次呼吁：檢查空輸入砸讳。
算法原型
我們先對著樣例思考一下如何解決這道題：
輸入：
s = "barfoothefoobarman",
words = ["foo","bar"]
輸出：[0,9]
- 不談動規(guī)琢融，那么必然是要用循環(huán)遍歷整個字串。
- 考慮到單詞的長度是相同的簿寂，我們可以記錄下單詞的長度
wlen漾抬，然后在循環(huán)檢測的過程中，我們可以讓步長直接為wlen常遂。
wlen == 3
in loop k:
...foobar...
↑
in loop k + 1
...foobar...
↑
- 為了記錄當前到底檢測通過了幾個詞纳令，我們可以設(shè)置一個計數(shù)器，記錄已經(jīng)記錄了多少個詞克胳。如果計數(shù)器等于
words的長度泊碑，那么就證明我們已經(jīng)完成了目標
words = ['bar', 'foo']
#wordsLen == 2
counter = 0
in loop 0:
barfoo...
↑
counter == 1
in loop 1:
barfoo
↑
counter == 2 == wordsLen
此時counter == wordsLen，因此ans里面就增加一個0毯欣。
- 如果我們遇到了詞表外的單詞馒过，比如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
然后我們著手優(yōu)化這個原型。
優(yōu)化1：words有重復(fù)詞
原題的樣例2就已經(jīng)告訴我們着裹，words內(nèi)是可以重復(fù)的：
輸入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
輸出：[]
那么該如何處理這個問題领猾？我們可以考慮把計數(shù)器counter改成一個字典，記錄下已經(jīng)記錄過了什么詞骇扇，以及記錄過了多少詞摔竿。
#設(shè)置比較對象
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 = {}
應(yīng)當指出，從這里開始少孝，substrHead是通過計算counter所記錄詞的個數(shù)继低，計算字串開頭在哪里。這對之后的優(yōu)化非常有幫助稍走。
foobarbarthe
↑
i
對于不同的counter：
{'bar': 2, 'foo': 1} - substrHead(i) == 0
{'bar': 2, 'foo': 0} - substrHead(i) == 3
優(yōu)化2：考慮詞數(shù)過多
樣例2中有這么一段：
wordgoodgoodgood...
顯然袁翁，這里有太多good了。正好婿脸，我們在上面已經(jīng)設(shè)置了一個字典粱胜，只要判斷一下是否超過allwords里面的數(shù)字就行。
if word in words:
if counter.get(word, 0) + 1 > allwords[word]:
counter = {}
counter[word] = 1
else:
counter[word] = counter.get(word, 0) + 1
重要優(yōu)化1：考慮重疊的可行解
在樣例1中狐树，可行解是這樣的：
[barfoo]the[foobar]man
然而年柠，如果我們輸入：
'barfoothebarfoo'
['bar', 'foo', 'the']
你會發(fā)現(xiàn)，我們算法只能發(fā)現(xiàn)下面的可行解：
[barfoothe]barfoo
因為我們在檢測之后褪迟，就跳過了之前的全部字串！然而答憔，真實的可行解是這樣的：
[barfoothe]barfoo
bar[foothebar]foo
barfoo[thebarfoo]
為了解決這個問題味赃，我們可以做出進一步的改進。
需要用暴力的方法去一個一個鑒別嗎虐拓？那么我們就浪費了很多中間已經(jīng)檢測成立的信息心俗。所以，我們可以將檢測區(qū)域想象一個滑動的區(qū)域蓉驹，在一個可行解成立的時候城榛，我們只需要把字串頭前移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
優(yōu)化3：可行解與冗余詞的重疊
再看樣例2。重復(fù)的單詞瞻润，如果不是word喘垂，而是good甜刻，那么會發(fā)生什么呢？
在目前的算法下正勒，會出現(xiàn)這樣的情況：
[wordgoodgood]goodbestword
↑
詞數(shù)過多得院，我們清空了counter，然后發(fā)現(xiàn)章贞，剩下的goodbestword組不成可行解祥绞。
但是，我們自己看鸭限，是能看到可行解在哪里的：
wordgood[goodgoodbestword]
利用我們剛才滑動區(qū)域的思想蜕径，其實也可以解決這個問題。當詞數(shù)超出限制里覆，將字串頭移動到詞數(shù)符合限制為止即可丧荐。
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
↑
重要優(yōu)化2：不定長的表外詞
其實我們剛才的討論都基于一個假設(shè)：表外單詞是定長的，和表內(nèi)單詞長度相同喧枷。但是虹统，題目只提出了表內(nèi)單詞同長，并沒有提出表外單詞同長隧甚。所以车荔，該怎么解決像這樣的問題呢：
輸入：
s = "barfoothetafoobar",
words = ["foo","bar"]
我們已經(jīng)做了這么多優(yōu)化了，難道前功盡棄戚扳，重歸暴力嗎忧便？當然不行，記住帽借，要充分利用花了時間處理過的信息珠增。
我們剛才的算法處理了什么東西？是步長為wlen的條件下砍艾，整個字符串的可行解蒂教。
重點是，如果求過了s的可行解脆荷，再去求s[wlen:]的可行解凝垛，有什么區(qū)別？除了0蜓谋，兩組可行解沒有區(qū)別梦皮！
這就意味著，我們不需要將從頭到尾遍歷字符串桃焕，作為算法的開頭剑肯，而是只需要遍歷s[:wlen]就可以了！
例如观堂，當遍歷計數(shù)器j == 0時：
[bar][foo][the][taf][oob]ar
^^^^^^^^^^
而當j == 2時：
ba[rfo][oth][eta][foo][bar]
^^^^^^^^^^
據(jù)此修改的代碼如下：
for j in range(wlen):
i = j
while i + wlen < slen:
...
i += wlen
return ans
最終代碼
經(jīng)過以上針對原型的優(yōu)化退子，相信你也可以自己寫出這題的正確代碼了岖妄。這里提供一份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)
這里還提供了一個小優(yōu)化：for i in range(min(lenword,lenstr-lensubstr+1)):，對應(yīng)我們剛才說的寂祥，就是單詞較長的時候荐虐，我們可以只需要遍歷到最終字串的長度已經(jīng)觸及字符串總長度的時候停下來：
"aaaaabbbbbcccccdd"
['aaaaa','bbbbb','ccccc']
lenword == wlen == 5
lenstr - lensubstr + 1 == slen - wlen * words + 1 == 3
取后者即可。
感謝閱讀丸凭！
