与所有单词相关联的字串 -

题目

https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/description/

给定一个字符串 s 和一些长度相同的单词 words，找出 s 与 words 中所有单词（words 每个单词只出现一次）串联一起（words 中组成串联串的单词的顺序随意）的字符串匹配的所有起始索引，子串要与串联串完全匹配，中间不能有其他字符。

举个例子，给定：

s：”barfoothefoobarman”

words：[“foo”, “bar”]

你应该返回的索引: [0,9]。（任意顺序）

题解

代码写的比较清楚，应该不需要题解。。

code

class Solution:
    def match(self, ss, word_dic):
        len_ss = len(ss)
        word_number = 
        i = 
        while True:
            word = ss[i:i+self.len_of_word]
            # keys() update
            if word in word_dic:
                if word_dic[word] > :
                    word_dic[word] -= 1
                    word_number += 1
                    # is update
                    if word_number is self.len_of_words:
                        return True
                # repeat
                else:
                    return False
            # not exist
            else:
                return False
            i += self.len_of_word
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        self.len_of_word = len(words[])
        self.len_of_words = len(words)
        self.len_of_str = len(s)
        a = dict()
        for word in words:
            if word in a:
                a[word] = a[word] + 1
            else:
                a.update({word: 1})
        index_recorder = []
        len_substr = self.len_of_word * self.len_of_words
        search_range = self.len_of_str - len_substr + 1
        for i in range(search_range):
            ss = s[i:i+len_substr]
            word_dic = a.copy()
            if self.match(ss, word_dic):
                index_recorder.append(i)
        return index_recorder
if __name__ == '__main__':
    s = "wordgoodgoodgoodbestword"
    words = ["word","good","best","good"]
    so = Solution()
    print(so.findSubstring(s, words))

算法 algorithm