567. 字符串的排列（中）

• 题目
• 题解：滑动窗口

题目

• 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
  换句话说，s1 的排列之一是 s2 的 子串

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false

题解：滑动窗口

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        need={}# 存储字符串 t 中各个字符的需求量
        window={}# 存储滑动窗口中各个字符的出现次数
        for c in s1:#遍历字符串t
            need.setdefault(c,0)#访问不存在的键时自动创建并将值设置为 0
            need[c]+=1# 统计字符串 t 中各个字符的需求量
        left=0# 滑动窗口的左指针
        right=0# 滑动窗口的右指针
        valid=0# 记录满足需求的字符数
        while right<len(s2):
            c=s2[right]# 当前字符
            right+=1# 右指针右移
            if c in need:#当前字符是目标字符中的
                window.setdefault(c,0)#访问不存在的键时自动创建并将值设置为 0
                window[c]+=1# 更新滑动窗口中当前字符的出现次数
                if window[c]==need[c]:# 如果滑动窗口中当前字符的出现次数达到需求量，增加满足需求的字符数
                    valid+=1
            while right -left>=len(s1):#当窗口大小大于s1时
                if valid == len(need):#每个字符的次数都达到了要求
                    return True
                d=s2[left] # 将要移出窗口的字符
                left+=1# 左指针右移
                if d in need:#当前字符是目标字符中的
                    if window[d]== need[d]:#如果滑动窗口中当前字符等于目标字符的值
                        valid-=1# 如果移出窗口的字符导致窗口不再满足需求，则减少满足需求的字符数
                    window[d]-=1# 更新滑动窗口中移出字符的出现次数
        return False