[Leetcode][python]Substring with Concatenation of All Words/与所有单词相关联的字串

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        s_length = len(s)
        word_num = len(words)
        word_length = len(words[0])
        words_length = word_num * word_length
        result = []
        words_dict = {}
        for word in words:  # 将words中的词语加入words_dict，存在则+1，不存在则设为1
            words_dict[word] = words_dict[word] + 1 if word in words_dict else 1
        for i in range(word_length):  # 以单词长度为i的范围，例如长度为3，则为0,1,2位置分别开始遍历
            left = i
            right = i
            curr_dict = {}
            while right + word_length <= s_length:  # 右指针未超出s长度时
                word = s[right:right + word_length]  # 提取word长度单词
                right += word_length  # 右指针往后一个word长度
                if word in words_dict:
                    curr_dict[word] = curr_dict[word] + 1 if word in curr_dict else 1  # 将本次遍历单词存入临时dict
                    while curr_dict[word] > words_dict[word]:  # 一旦临时dict中该单词数量大于本该有的数量，说明这一串匹配不成功
                        # 需要从最左边开始不断吐出单词，直到超过数量的单词，在这里while可以不断进入直到word这个单词的数量被减少
                        curr_dict[s[left:left + word_length]] -= 1  # 从左指针开始，逐个减去每个word出现的数量
                        left += word_length
                    if right - left == words_length:  # 如果子串长度和words长度相同，说明成功匹配
                        result.append(left)
                else:  # 出现不在word中单词，清空临时dict，恢复指针
                    curr_dict.clear()
                    left = right
        return result