給定一個字符串 s 和一些長度相同的單詞 words。在 s 中找出可以恰好串聯(lián) words 中所有單詞的子串的起始位置。

注意子串要與 words 中的單詞完全匹配，中間不能有其他字符，但不需要考慮 words 中單詞串聯(lián)的順序。

示例 1:

輸入:
s = "barfoothefoobarman",
words = ["foo","bar"]
輸出: [0,9]
解釋: 從索引 0 和 9 開始的子串分別是 "barfoor" 和 "foobar" 。
輸出的順序不重要, [9,0] 也是有效答案。

class Solution:
    def findSubstring(self, s, words):
        dic_words = {}
        if not (s and words):
            return []
        for word in words:
            if word in dic_words:
                dic_words[word] += 1
            else:
                dic_words[word] = 1
        len_s = len(s)
        len_word = len(words[0])
        count_words = len(words)
        res = []
        for i in range(len_s - count_words * len_word + 1):
            j = 0
            dic_tmp = {}
            while j < count_words:  # 把單詞數(shù)量都取完
                tmp_word = s[i + j * len_word: i + (j + 1) * len_word]
                if tmp_word not in dic_words: # 如果不在目標(biāo)字典就退出
                    break
                if tmp_word in dic_words and tmp_word not in dic_tmp:
                    dic_tmp[tmp_word] = 1
                else:
                    dic_tmp[tmp_word] += 1
                    if dic_tmp[tmp_word] > dic_words[tmp_word]: # 如果超過單詞數(shù)量就退出
                        break
                j += 1
            else: # 循環(huán)完成后表示所有單詞都統(tǒng)計完成
                res.append(i)
        return res


su = Solution()
s = "wordgoodgoodgoodbestword"
words = ["word", "good", "best", "word"]
res = su.findSubstring(s, words)
print(res)