567. 字符串的排列 Medium
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的 排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
示例 2：
输入：s1= "ab" s2 = "eidboaoo"
输出：false
解题思路
输入：两个字符串 s1 和 s2
输出：判断 s2 中是否存在 s1 的一个排列子串
本题属于固定长度滑动窗口类型问题。
我们可以使用一个长度为 s1 的滑动窗口在 s2 上移动，并在窗口内实时统计字符频率。同时，使用两个计数器（数组或哈希表）分别记录 s1 和当前窗口中每个字母出现的次数。每次窗口移动时，只需更新进入和移出的字符计数，然后比较两个计数器是否相等。若某一时刻窗口内字符频率与 s1 完全一致，则说明找到了一个有效排列，返回 True。如果遍历结束仍未找到，返回 False。
本题难点在于要想到用数组或者哈希对比窗口内字母出现次数的逻辑。
代码实现
python
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
len_s1, len_s2 = len(s1), len(s2)
if len_s1 > len_s2:
return False
count1 = [0] * 26 # 统计 s1 中每个字符的出现次数
count2 = [0] * 26 # 滑动窗口中 s2 的字符统计
for i in range(len_s1):
count1[ord(s1[i]) - ord('a')] += 1
count2[ord(s2[i]) - ord('a')] += 1
# 开始滑动窗口
for i in range(len_s2 - len_s1):
if count1 == count2:
return True
# 移除左边的字符，添加右边的字符
count2[ord(s2[i]) - ord('a')] -= 1
count2[ord(s2[i + len_s1]) - ord('a')] += 1
# 别忘了最后一轮窗口的比较
return count1 == count2javascript
// 判断 s2 中是否包含 s1 的任意一个排列
var checkInclusion = function(s1, s2) {
const n1 = s1.length; // s1 的长度
const n2 = s2.length; // s2 的长度
if (n1 > n2) return false; // 如果 s1 比 s2 长，肯定不可能包含，直接返回 false
// 统计 26 个字母的频率数组
const count1 = Array(26).fill(0); // s1 的字符频率
const count2 = Array(26).fill(0); // s2 的窗口字符频率
// 初始化：先统计 s1 和 s2 的前 n1 个字符的频率
for (let i in s1) {
count1[s1[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
count2[s2[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
}
// 滑动窗口：窗口大小固定为 n1，从左到右滑动
for (let j = 0; j < n2 - n1; j++) {
// 每次比较两个频率数组，如果相同说明找到了排列
if (isEqual(count1, count2)) {
return true;
}
// 窗口右移：移除左边一个字符，加入右边一个字符
count2[s2[j].charCodeAt(0) - 'a'.charCodeAt(0)] -= 1; // 移除左边
count2[s2[j + n1].charCodeAt(0) - 'a'.charCodeAt(0)] += 1; // 加入右边
}
// 循环结束后，最后一个窗口还需要再比较一次
return isEqual(count1, count2);
};
// 判断两个频率数组是否完全相同
function isEqual(list1, list2) {
for (let i in list1) {
if (list1[i] !== list2[i]) {
return false; // 有一个不一样就返回 false
}
}
return true; // 全部相同则返回 true
}复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)