438. 找到字符串中所有字母异位词#

题目描述#

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。所谓异位词，即字符构成相同、排列顺序不同的词。

示例：

1
输入：s = "cbaebabacd", p = "abc"
2
输出：[0, 6]

解法思路#

核心思想：与 567 完全相同的”定长滑窗 + 计数归零”套路，只是把”找到一次就返回”改成”每次匹配都记录起始下标”。

窗口长度固定为 n = len(p)，维护差值数组 cnt[26] 与 non_zero 计数：

预处理 p：cnt[c] -= 1；
入窗口 +1、出窗口 -1。

当窗口长度达到 n（即 i >= n-1）且 non_zero == 0 时，说明窗口 [i-n+1, i] 内是 p 的一个异位词，把起始下标 i-n+1 加入答案。

逐步举例（s="cbaebabacd", p="abc"，n=3）：

初始化 cnt['a']=cnt['b']=cnt['c']=-1，non_zero=3。
i=2，窗口形成 [0,2]="cba"：三个字符差值在此过程全部归零，non_zero=0 → append(2-3+1=0)。
i=8，窗口 [6,8]="bac"：又一轮让非零清零，non_zero=0 → append(8-3+1=6)。
最终返回 [0, 6] ✓

复杂度分析#

时间复杂度：O(n)，n = len(s)。
空间复杂度：O(1)，固定 26 长计数数组。

代码实现#

1
class Solution:
2
    def findAnagrams(self, s: str, p: str) -> list[int]:
3
        n, m = len(p), len(s)
4
        if n > m:
5
            return []
6

7
        cnt = [0] * 26
8
        for c in p:
9
            cnt[ord(c) - 97] -= 1
10

11
        non_zero = sum(1 for v in cnt if v != 0)
12
        ans = []
13

14
        for i, c in enumerate(s):
15
            idx = ord(c) - 97
16
            old = cnt[idx]
17
            cnt[idx] += 1
18
            if old == 0:
19
                non_zero += 1
20
            elif cnt[idx] == 0:
21
                non_zero -= 1
22

23
            if i >= n:
24
                idx2 = ord(s[i - n]) - 97
25
                old2 = cnt[idx2]
26
                cnt[idx2] -= 1
27
                if old2 == 0:
28
                    non_zero += 1
29
                elif cnt[idx2] == 0:
30
                    non_zero -= 1
31

32
            if i >= n - 1 and non_zero == 0:
33
                ans.append(i - n + 1)
34

35
        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 TestFindAnagrams(unittest.TestCase):
10
    def setUp(self):
11
        self.solution = Solution()
12

13
    def test_example1(self):
14
        self.assertEqual(self.solution.findAnagrams("cbaebabacd", "abc"), [0, 6])
15

16
    def test_example2(self):
17
        self.assertEqual(self.solution.findAnagrams("abab", "ab"), [0, 1, 2])
18

19
    def test_no_anagram(self):
20
        self.assertEqual(self.solution.findAnagrams("abcdef", "ghi"), [])
21

22
    def test_p_larger_than_s(self):
23
        self.assertEqual(self.solution.findAnagrams("a", "ab"), [])
24

25
    def test_same_string(self):
26
        self.assertEqual(self.solution.findAnagrams("abc", "abc"), [0])
27

28
    def test_duplicate_chars(self):
29
        self.assertEqual(self.solution.findAnagrams("aaa", "aa"), [0, 1])
30

31

32
if __name__ == "__main__":
33
    unittest.main()