Leetcode題解 Python：Substring with Concatenation of All Words

給一字串 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