30. 串联所有单词的子串#

题目描述#

给定一个字符串 s 和一个字符串数组 words，其中 words 中所有字符串长度相同。在 s 中找到所有子串的起始索引，这些子串是 words 中每个单词恰好一次、无间隔地串联而成的排列。

示例：

1
输入：s = "barfoothefoobarman", words = ["foo","bar"]
2
输出：[0,9]（子串 [0,6)="barfoo"，[9,15)="foobar"）

解法思路#

核心思想：把每个单词当作一个”超级字符”，问题就退化成了 438 的异位词滑窗。

由于所有单词等长 word_len，正确的串联子串一定从某一个 offset（0..word_len-1）开始，且该子串按 word_len 切分后，得到的单词序列必须与 words 的计数一致。因此分 word_len 组分别做滑窗：

对每个 offset，把 s 按 word_len 切成单词序列 w；
维护窗口内单词计数字典 cur 和一个 valid 变量，记录频次恰好匹配的单词种类数；
入单词：cur[w]++，若正好等于 target[w]，valid+1；
出单词（窗口总长超过 total_len = len(words)*word_len 时）：cur[w_left]--，若先前正好匹配则 valid-1；
遇到不在 target 中的单词，直接清空窗口重置；
当 valid == len(target)，当前起点 left 就是一个合法子串起点。

逐步举例（s="barfoothefoobarman", words=["foo","bar"]，word_len=3, total_len=6，只看 offset=0 分组）：

切分出的单词序列：bar foo the foo bar man。
入 "bar"：cur[bar]=1==target[bar]，valid=1。
入 "foo"：cur[foo]=1==target[foo]，valid=2==len(target) → append(0) ✓。
入 "the"（不在 target）→ 清空窗口，left 跳到其后。
最终 offset=0 得到起点 0；offset=3 分组还会得到起点 9。

复杂度分析#

时间复杂度：O(n·word_len)，每组各做一次 O(n/word_len) 遍历。
空间复杂度：O(n)，哈希表存储单词计数。

代码实现#

1
class Solution:
2
    def findSubstring(self, s: str, words: list[str]) -> list[int]:
3
        word_len = len(words[0])
4
        word_count = len(words)
5
        total_len = word_len * word_count
6
        n = len(s)
7
        if n < total_len:
8
            return []
9

10
        from collections import Counter
11
        target = Counter(words)
12
        ans = []
13

14
        for offset in range(word_len):
15
            left = offset
16
            cur = {}
17
            valid = 0
18

19
            for right in range(offset, n - word_len + 1, word_len):
20
                w = s[right:right + word_len]
21

22
                if w not in target:
23
                    cur.clear()
24
                    valid = 0
25
                    left = right + word_len
26
                    continue
27

28
                cur[w] = cur.get(w, 0) + 1
29
                if cur[w] == target[w]:
30
                    valid += 1
31

32
                while right - left + word_len > total_len:
33
                    w_left = s[left:left + word_len]
34
                    if cur[w_left] == target[w_left]:
35
                        valid -= 1
36
                    cur[w_left] -= 1
37
                    left += word_len
38

39
                if valid == len(target):
40
                    ans.append(left)
41

42
        return ans

1
import sys
2
import unittest
3
from pathlib import Path
4

5
sys.path.insert(0, str(Path(__file__).parent))
6
from solution import Solution
7

8

9
class TestFindSubstring(unittest.TestCase):
10
    def setUp(self):
11
        self.solution = Solution()
12

13
    def test_example1(self):
14
        self.assertEqual(
15
            self.solution.findSubstring("barfoothefoobarman", ["foo", "bar"]),
16
            [0, 9]
17
        )
18

19
    def test_example2(self):
20
        self.assertEqual(
21
            self.solution.findSubstring("wordgoodgoodgoodbestword", ["word", "good", "best", "word"]),
22
            []
23
        )
24

25
    def test_example3(self):
26
        self.assertEqual(
27
            self.solution.findSubstring("barfoofoobarthefoobarman", ["bar", "foo", "the"]),
28
            [6, 9, 12]
29
        )
30

31
    def test_empty_result(self):
32
        self.assertEqual(
33
            self.solution.findSubstring("abc", ["d", "e"]),
34
            []
35
        )
36

37
    def test_single_word(self):
38
        self.assertEqual(
39
            self.solution.findSubstring("aaaa", ["a"]),
40
            [0, 1, 2, 3]
41
        )
42

43
    def test_duplicate_words(self):
44
        self.assertEqual(
45
            self.solution.findSubstring("aaa", ["a", "a"]),
46
            [0, 1]
47
        )
48

49

50
if __name__ == "__main__":
51
    unittest.main()