給一字串 s 跟 words 字串串列，問哪些位置可以找到全部在words中的詞只出現一次。
思路很簡單，想辦法在一個 n 的時間讓全部都搜過。(用搜尋法倒很隨意)
有一個條件可以利用，那就是每個 word 都是一樣的長度，因此不必逐字元去判斷，可以拿詞去匹配。
於是產生原型的逐詞匹配，但這還不夠！速度還太慢。
每當遇到這種匹配題型，盡可能不要反覆同一位置重複匹配。之前有提到一個方式 KMP，若全照用，這裡可能會在 prefix table 產生太多組合 。
因為 words 的詞沒有指定先後順序，所以要是當前位置沒有匹配到，就可把最前面匹配的放回待匹配的隊伍，繼續匹配，若都沒有可匹配，那就往下移動。
Python(逐詞匹配)
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
result = []
if not s or not words: return result
counter = Counter(words)
nowCounter = counter.copy()
i = 0
m = len(words[0])
n = len(s)
n2 = len(words)
while i <= n-m*n2:
nowCounter = counter.copy()
for j in range(n2):
word = s[i+j*m:i+m+j*m]
if word in nowCounter:
if nowCounter[word] > 0:
nowCounter[word] -= 1
if nowCounter[word] == 0:
del nowCounter[word]
else:
break
if not nowCounter: result.append(i)
i += 1
return result
Python(逐詞匹配2)
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
result = []
if not s or not words: return result
wl = len(words[0])
wn = len(words)
counter = Counter(words)
select = list()
n = len(s)
def search(pos, wi):
if pos+wl > n:
while select: counter[select.pop(0)] += 1
return
word = s[pos: pos+wl]
while select and (word not in counter or counter[word] == 0):
counter[select.pop(0)] += 1
wi -= 1
if word in counter and counter[word] > 0:
counter[word] -= 1
select.append(word)
if wi+1 == wn: result.append(pos - wi*wl)
search(pos+wl, wi+1)
else:
search(pos+wl, wi)
for i in range(wl):
search(i, 0)
return result