30. 串联所有单词的子串

WrRan / 2024-09-17 / 原文

题目链接	30. 串联所有单词的子串
思路	滑动窗口
题解链接	官方题解
关键点	线性平移的动作；有明确状态量；应当使用滑动窗口
时间复杂度	$O(\text{len}(\text{words}_0))\times\text{len}(s))$
空间复杂度	$O(\text{len}(\text{words}_0)\times\#\text{words})$

代码实现：

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        answer = []
        m = len(words)
        n = len(words[0])
        ls = len(s)

        for i in range(n):
            if i + m * n > ls:
                break
            diff = defaultdict(int)
            for j in range(m):
                word = s[i + j * n : i + (j+1) * n]
                diff[word] += 1
            for word in words:
                diff[word] -= 1
                if diff[word] == 0:
                    del diff[word]
            
            for start in range(i, ls-m*n+1, n):
                if start != i:
                    word = s[start + (m-1)*n: start + m*n]
                    diff[word] += 1
                    if diff[word] == 0:
                        del diff[word]
                    word = s[start - n: start]
                    diff[word] -= 1
                    if diff[word] == 0:
                        del diff[word]
                if len(diff) == 0:
                    answer.append(start)

        return answer