567. 字符串的排列#

题目描述#

给你两个字符串 s1 和 s2，判断 s2 是否包含 s1 的排列。若是返回 true，否则返回 false。即是否存在一个长度为 len(s1) 的子串，其字符出现次数与 s1 完全一致（顺序可不同）。

示例：

1
输入：s1 = "ab", s2 = "eidbaooo"
2
输出：true（子串 "ba" 是 "ab" 的排列）

解法思路#

核心思想：定长滑窗 + 计数归零判定。

s1 的排列与原串只是顺序不同、字符频次相同。于是开一个长 n=len(s1) 的定长窗口，维护窗口内各字符频次与 s1 频次的差值数组 cnt[26]：

预处理 s1：cnt[c] -= 1（表示 s1 需要这么多字符）；
滑窗时，左出窗口的字符 -1，右进窗口的字符 +1。

当某个字符的差值回到 0，说明窗口内该字符的个数已与 s1 对齐。若所有 26 个字符差值都为 0，则窗口内就是 s1 的一个排列。

为了避免每次遍历 26 个字符，用一个 non_zero 变量记录 cnt 中非零项的个数：

某字符从 0 变非 0，non_zero+1；
从非 0 变 0，non_zero-1。

当 non_zero == 0，直接返回 true，O(1) 完成匹配判断。

逐步举例（s1="ab", s2="eidbaooo"，窗口长 n=2）：

初始化 cnt['a']=-1, cnt['b']=-1，non_zero=2。
i=3 入 'b'：cnt['b']:-1→0，non_zero=2→1；出 s2[1]='i'：cnt['i']:→0，non_zero=1。
i=4 入 'a'：cnt['a']:-1→0，non_zero=1→0。此时窗口覆盖 [3,4]="ba"，正是 "ab" 的排列 → return true ✓

复杂度分析#

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

代码实现#

1
class Solution:
2
    def checkInclusion(self, s1: str, s2: str) -> bool:
3
        n, m = len(s1), len(s2)
4
        if n > m:
5
            return False
6

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

11
        non_zero = sum(1 for v in cnt if v != 0)
12

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

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

31
            if i >= n - 1 and non_zero == 0:
32
                return True
33
        return False

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

13
    def test_example1(self):
14
        self.assertTrue(self.solution.checkInclusion("ab", "eidbaooo"))
15

16
    def test_example2(self):
17
        self.assertFalse(self.solution.checkInclusion("ab", "eidboaoo"))
18

19
    def test_same_string(self):
20
        self.assertTrue(self.solution.checkInclusion("abc", "abc"))
21

22
    def test_s1_larger_than_s2(self):
23
        self.assertFalse(self.solution.checkInclusion("abc", "ab"))
24

25
    def test_duplicate_chars(self):
26
        self.assertTrue(self.solution.checkInclusion("aab", "baa"))
27

28
    def test_single_char(self):
29
        self.assertTrue(self.solution.checkInclusion("a", "a"))
30
        self.assertFalse(self.solution.checkInclusion("a", "b"))
31

32

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