与所有单词相关联的字串


目录

题目

  • 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 = 0
        i = 0
        while True:
            word = ss[i:i+self.len_of_word]
            # keys() update
            if word in word_dic:
                if word_dic[word] > 0:
                    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[0])
        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))

除非另有声明,本网站采用知识共享“ 署名-非商业性使用-相同方式共享 3.0 中国大陆 ”许可协议授权。

tag:  #算法