LeetCode_30_困难_串联所有单词的子串

1. 题目

给定一个字符串 $s$ 和一个字符串数组 $words$。 $words$ 中所有字符串 长度相同。

$s$ 中的 串联子串 是指一个包含 $words$ 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 $words=["ab","cd","ef"]$， 那么 $"abcdef"，"abefcd"，"cdabef"，"cdefab"，"efabcd"，"efcdab"$ 都是串联子串。 $"acdbef"$ 不是串联子串，因为他不是任何 $words$ 排列的连接。

返回所有串联子串在 $s$ 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：$s="barfoothefoobarman",words=["foo","bar"]$
输出：$[0,9]$
解释：因为 $words.length==2$ 同时 $words[i].length==3$，连接的子字符串的长度必须为 $6$。
子串 $"barfoo"$ 开始位置是 $0$。它是 $words$ 中以 $["bar","foo"]$ 顺序排列的连接。
子串 $"foobar"$ 开始位置是 $9$。它是 $words$ 中以 $["foo","bar"]$ 顺序排列的连接。
输出顺序无关紧要。返回 $[9,0]$ 也是可以的。

示例 2：

输入：$s="wordgoodgoodgoodbestword",words=["word","good","best","word"]$
输出：$[]$
解释：因为 $words.length==4$ 并且 $words[i].length==4$，所以串联子串的长度必须为 $16$。
$s$ 中没有子串长度为 $16$ 并且等于 $words$ 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：$s="barfoofoobarthefoobarman",words=["bar","foo","the"]$
输出：$[6,9,12]$
解释：因为 $words.length==3$ 并且 $words[i].length==3$，所以串联子串的长度必须为 $9$。
子串 $"foobarthe"$ 开始位置是 $6$。它是 $words$ 中以 $["foo","bar","the"]$ 顺序排列的连接。
子串 $"barthefoo"$ 开始位置是 $9$。它是 $words$ 中以 $["bar","the","foo"]$ 顺序排列的连接。
子串 $"thefoobar"$ 开始位置是 $12$。它是 $words$ 中以 $["the","foo","bar"]$ 顺序排列的连接。

提示：

• $1<=s.length<=10^4$
• $1<=words.length<=5000$
• $1<=words[i].length<=30$
• $words[i]$ 和 $s$ 由小写英文字母组成

2. 思路及代码实现详解（Python）

2.1 滑动窗口

记 $\text{words}$ 的长度为 $m$，$\text{words}$ 中每个单词的长度为 $n$，$s$ 的长度为 $\text{ls}$。由于已知单词的长度和数量，因此可以直到串联子串的长度，并通过建立一个固定长度的窗口，并在不断滑动窗口的过程中，判断窗口中的固定长度字符串的出现次数是否与 $words$ 中的一致，如果一致，则获取窗口的开始索引位置。

具体做法是，首先需要将 $s$ 划分为单词组，每个单词的大小均为 $n$ （首尾除外）。这样的划分方法有 $n$ 种（$len(s)/n$ 的商的情况），即先删去前 $i$ （$i=0\sim n-1$）个字母后，将剩下的字母进行划分，如果末尾有不到 $n$ 个字母也删去。对这 $n$ 种划分得到的单词数组分别使用滑动窗口对 $\text{words}$ 进行搜寻，每次向右滑动 $n$ 个距离，直到 $s$ 右端剩余字符数不足 $n$。

划分成单词组后，一个窗口包含 $s$ 中从 $i$ 起始的前 $m$ 个单词，用一个哈希表 $\text{differ}$ 表示窗口中单词频次和 $\text{words}$ 中单词频次之差，当差值为 $0$ 时认为窗口中单词数量与 $words$ 当中单词数量一致。初始化 $\text{differ}$ 时，出现在窗口中的单词，每出现一次，相应的值增加 $1$，出现在 $\text{words}$ 中的单词，每出现一次，相应的值减少 $1$。然后将窗口右移，右侧会加入一个单词，左侧会移出一个单词，并对 $\text{differ}$ 做相应的更新。窗口移动时，若出现 $\text{differ}$ 中值不为 $0$ 的键的数量为 $0$，则表示这个窗口中的单词频次和 $\text{words}$ 中单词频次相同，窗口的左端点是一个待求的起始位置。划分的方法有 $n$ 种，做 $n$ 次滑动窗口后，即可找到所有可能的起始位置。

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        res = []
        m, n, ls = len(words), len(words[0]), len(s)
        for i in range(n):
            if i + m * n > ls:
                break
            differ = Counter()
            for j in range(m):
                word = s[i + j * n: i + (j + 1) * n]
                differ[word] += 1
            for word in words:
                differ[word] -= 1
                if differ[word] == 0:
                    del differ[word]
            for start in range(i, ls - m * n + 1, n):
                if start != i:
                    word = s[start + (m - 1) * n: start + m * n]
                    differ[word] += 1
                    if differ[word] == 0:
                        del differ[word]
                    word = s[start - n: start]
                    differ[word] -= 1
                    if differ[word] == 0:
                        del differ[word]
                if len(differ) == 0:
                    res.append(start)
        return res

该算法遍历了 $n$ 种窗口的左端起始位置，每次窗口滑动的时间复杂度为 $O(ls)$，总的渐进复杂度为 $O(ls\times n)$，空间复杂度为 $O(m\times n)$，主要是保存单词出现频次的哈希表开销。

执行用时：97 ms
消耗内存：11.21 MB

题解来源：力扣官方题解