【leetcode-Python】-滑动窗口-30. Substring with Concatenation of All Words

题目链接

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

题目描述

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例

输入：s = "barfoothefoobarman",words = ["foo","bar"]

输出：[0,9]

从索引0和9开始的子串分别是"barfoo"和"foobar"，输出的顺序不重要，[9,0]也是有效答案。

解题思路

还是子串问题，我们仍用滑动窗口去解决。由于words中单词长度相等，那么设置左右指针移动时只移动一个单词的长度。需要注意的是，应当在“窗口滑动”之前遍历窗口的起始位置。比如每个单词的长度为3，如果左右指针的起始位置为0，那么每次只移动一个单词长度的话，能访问到的只有以0、3、6、9,...这几个索引字母开头的单词。左右指针的起始位置为1时，每次只移动一个单词长度，能访问到的只有以1、4、7、10,...这几个索引字母开头的单词。左右指针的起始位置为2时，能访问到的只有2,5,8,11,...这几个索引字母开头的单词。因此需要遍历[0,len(one_word))设置左右指针的起始位置，这样能够遍历到以各个位置开头的单词，确保没有遗漏。

我们仍维护target来存储words中出现的各个单词的个数（需要凑齐的单词），window存储窗口中出现的words里单词的个数，valid存储window中满足target条件的单词个数。需要注意的是对于不同的窗口起始位置，window和valid要重新初始化。因为对于不同的窗口起始位置，window和valid将要存储新一轮的滑动结果。

右边界移动的条件为：右指针+一个单词的长度<=字符串s的长度(这样当右指针+一个单词长度=字符串s的长度时，右指针继续右移一个单词的长度，右指针等于len(s)，就不能继续移动了)。左指针移动的条件为窗口内的字母个数等于words中的字母个数，此时判断窗口内子串是否是words中单词的串联，并移动左指针。

Python实现

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        #左右指针每次移动len(word)的长度
        from collections import defaultdict
        target = defaultdict(int)
        for word in words:
            target[word] += 1
        one_word = len(words[0])
        words_len = len(words)*one_word
        result = []
        for i in range(0,one_word): #窗口的起始位置
            left = i 
            right = i
            valid = 0
            window = defaultdict(int)
            while(right + one_word <=len(s)):#右边界可以继续移动的条件
                #新加入窗口的单词
                new_word = s[right:right+one_word]
                right += one_word
                if new_word in target:
                    window[new_word]+=1
                    if window[new_word] == target[new_word]:
                        valid += 1
                while(right-left == words_len): #左边界移动的条件
                    #判断一下
                    if(valid == len(target)):
                        result.append(left)
                    #左移
                    tmp_word = s[left:left+one_word]
                    left += one_word
                    if tmp_word in target:
                        if(window[tmp_word] == target[tmp_word]):
                            valid -= 1
                        window[tmp_word] -= 1
        return result