leetcode 030. 与所有单词相关联的字串

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

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

示例 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:  # 把单词数量都取完
                tmp_word = s[i + j * len_word: i + (j + 1) * len_word]
                if tmp_word not in dic_words: # 如果不在目标字典就退出
                    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]: # 如果超过单词数量就退出
                        break
                j += 1
            else: # 循环完成后表示所有单词都统计完成
                res.append(i)
        return res


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