难度: Medium
给你两个字符串 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 <= 104s1 和 s2 仅包含小写字母运行时间: 66 ms
内存: 16.1 MB
from collections import Counter
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
window = {}
need = Counter(s1)
valid = 0
left,right = 0,0
while right < len(s2):
c = s2[right]
right += 1
if c not in need:
left = right
window = {}
valid = 0
else:
window[c] = window.get(c,0) + 1
if window[c] == need[c]:
valid += 1
while valid >= len(need):
if right-left == len(s1):
return True
d = s2[left]
left += 1
window[d] -= 1
if window[d] < need[d]:
valid -= 1
return False
这个题解使用了滑动窗口的思路。首先用 Counter 统计 s1 中每个字符出现的次数，作为需要满足的条件。然后在 s2 上滑动窗口，扩张和收缩窗口，并统计窗口内每个字符的出现次数。当窗口内某个字符的出现次数与 s1 中对应的次数相等时，说明找到了一个符合条件的字符。当所有字符都符合条件，且窗口大小等于 s1 的长度时，说明找到了一个 s1 的排列，返回 True。如果滑动到 s2 的末尾还没找到，则返回 False。
时间复杂度: O(n)
空间复杂度: O(1)
from collections import Counter
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
# 存储滑动窗口内每个字符出现的次数
window = {}
# 存储 s1 中每个字符出现的次数
need = Counter(s1)
# 记录滑动窗口内满足条件的字符个数
valid = 0
# 滑动窗口的左右指针
left,right = 0,0
while right < len(s2):
# 将 s2[right] 加入窗口
c = s2[right]
right += 1
# 如果 s2[right] 不在 s1 中，重置窗口
if c not in need:
left = right
window = {}
valid = 0
else:
# 更新窗口内字符出现的次数
window[c] = window.get(c,0) + 1
# 如果窗口内字符 c 的出现次数与 s1 中对应的次数相等，valid 加 1
if window[c] == need[c]:
valid += 1
# 如果窗口内所有字符都满足条件，判断窗口大小是否等于 s1 的长度
while valid >= len(need):
if right-left == len(s1):
return True
# 将 s2[left] 移出窗口
d = s2[left]
left += 1
# 更新窗口内字符出现的次数
window[d] -= 1
# 如果窗口内字符 d 的出现次数小于 s1 中对应的次数，valid 减 1
if window[d] < need[d]:
valid -= 1
return False
在检查窗口内字符数量满足s1中字符数量要求后，比较窗口大小和s1的长度可以确认窗口中不包含额外的字符，确保窗口恰好是s1的一个排列。如果窗口大小大于s1长度，则窗口中必然包含不属于s1排列的额外字符，这不符合题目要求。
当遇到s2中不在s1中的字符时，重置窗口是为了清除所有与s1不匹配的字符的影响，因为这些字符的存在无法形成s1的排列。简单移动左指针可能仍然包含那些不相关的字符，而重置窗口能确保重新开始寻找可能的s1排列，提高效率并简化逻辑。
本算法通过使用字符计数器来统计窗口内和s1中的字符数，只要这些字符的计数相匹配，就可以认为窗口内的字符是s1的一个排列。这种方法只关注字符数量的匹配，并不关心字符的实际顺序，因此可以有效地判断是否存在符合条件的排列而无需考虑字符顺序。
在滑动窗口算法中，valid变量用于记录窗口内满足s1中字符数量要求的字符种类数。当valid值等于s1中不同字符的种类数时，表示窗口内所有必需的字符都已达到所需数量，此时如果窗口大小恰好等于s1长度，则可以确定这个窗口是s1的一个排列。valid变量是判断窗口状态是否完全满足题目要求的关键因素。