华为 OD 训练营 · 题解精讲
LC567. 字符串的排列
LC567. 字符串的排列
题目描述
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。 换句话说，s1 的排列之一是 s2 的 子串 。 示例 1： 输入：s1 = "ab" s2 = "eidbaooo" 输出：true 解释：s2 包含 s1 的排列之一 ("ba"). 示例 2： 输入：s1= "ab" s2 = "eidboaoo" 输出：false 提示： 1 <= s1.length, s2.length <= 104 s1 和 s2 仅包含小写字母
题目解析
解题思路
本题判断 s2 是否包含 s1 的某个排列作为子串。由于排列不改变字符种类和频次，只需判断 s2 中是否存在一个长度等于 s1 的连续子串，其字符频次与 s1 完全相同。
采用固定长度滑动窗口算法。窗口长度固定为 len(s1)，在 s2 上从左到右滑动，每次比较窗口内字符频次与 s1 的字符频次是否相等。若相等则返回 true。
数据结构：使用两个哈希表（Counter）分别记录 s1 的字符频次和当前窗口的字符频次。
关键步骤
1. 初始化：计算 s1 的频次表 cnt1，以及 s2 第一个窗口（前 k 个字符）的频次表 cnt2。若两者相等则直接返回 true。 2. 滑动窗口：从索引 k 开始遍历 s2 剩余字符：
- 将新进入窗口的字符
ch加入cnt2 - 将离开窗口的字符
left_ch从cnt2中移除（频次减 1，若减为 0 则删除该键） - 比较
cnt1 == cnt2，若相等则返回 true
3. 遍历结束返回 false。
示意图（以 s1="ab", s2="eidbaooo" 为例）：
窗口长度 k=2
初始窗口: [e,i] → cnt2 ≠ cnt1
滑动一步: [i,d] → 不等
滑动一步: [d,b] → 不等
滑动一步: [b,a] → cnt2 == cnt1 → true复杂度分析
- 时间复杂度：O(n + m)，其中 n = len(s2)，m = len(s1)。初始化 cnt1 需 O(m)，滑动窗口遍历 s2 需 O(n)，每次比较两个 Counter 的键值对数量不超过 26（小写字母），可视为 O(1)。
- 空间复杂度：O(1)，两个 Counter 最多存储 26 个键值对。
参考代码
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
# 滑动窗口模板化解题，五步走策略
# 【1、定义需要维护的变量】
# 题目要求返回这些子串的起始索引，因此使用数组来保存结果，存储的是整型
res = []
# 由于都是小写字母，因此直接用 26 个长度的数组代替原来的 HashMap ，比直接使用 HashMap 更优秀
# needs 代表 p 中每个字符出现的频次
needs = [0] * 26
# 开始统计 t 中每个字符出现的频次
for ch in s1:
# 对于数组类型，其下标为 int 类型
# 可以直接使用 char 类型变量，默认强制转换，存储的就是字母对应的 ASCII 码
# 比如 ch 是 b 字符，那么 b - a = 1，即 needs[1] 表示记录 b 出现的频次
idx = ord(ch) - ord('a')
needs[idx] += 1
# window 代表在滑动窗口中每个字符出现的频次
window = [0] * 26
# 【2、定义窗口的首尾端 (start, end)， 然后滑动窗口】
# 窗口的左端位置从 0 开始
start = 0
# 窗口的右端位置从 0 开始，可以一直移动到尾部
for end in range(len(s2)):
# 【3、更新需要维护的变量, 有的变量需要一个 if 语句来维护 (比如最大最小长度)】
# 获取此时将要加入到滑动窗口的元素
cur = s2[end]
# 这个字符的频次需要发生变化
window[ord(cur) - ord('a')] += 1
# 加入之后，去对比一下 window 中 cur 这个字符是否满足要求
if window == needs:
# 相同情况下，找到一个符合条件的索引
return True
# 【4、如果题目的窗口长度固定：用一个 if 语句判断一下当前窗口长度是否达到了限定长度 】
# 4.1、如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变,
if end >= len(s1) - 1 :
# 4.2、更新 (部分或所有) 维护变量
chr = s2[start]
# 最左端那个元素的频次发生变化
window[ord(chr) - ord('a')] -= 1
# 4.3、窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变
start += 1
# 【5、返回所需要的答案】
return False
代码
# 题目：LC567. 字符串的排列
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：固定滑窗
# 代码看不懂的地方，请直接在群上提问
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
# 固定窗口长度
k = len(s1)
# 初始化两个用于计数的哈希表cnt1，cnt2
cnt1 = collections.Counter(s1)
# cnt2初始化为第一个滑窗里包含元素的结果
cnt2 = collections.Counter(s2[:k])
# 判断第一个窗口的结果
if cnt1 == cnt2:
return True
for right, ch in enumerate(s2[k:], k):
# A1
cnt2[ch] += 1
# A2
left_ch = s2[right-k]
cnt2[left_ch] -= 1
if cnt2[left_ch] == 0:
del cnt2[left_ch]
# A3
if cnt1 == cnt2:
return True
return False