567. 字符串的排列

Difficulty
Medium
Tags
滑动窗口
双指针
URL
https://leetcode-cn.com/problems/permutation-in-string/
Star
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，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 仅包含小写字母

滑动窗口

思路
类似
🏅
76. 最小覆盖子串 ，只不过本题收缩窗口的时机不同，因为本体严格限制了是子串，所以窗口的大小不能大于s1的长度。然后在这个固定窗口内判断valid
题解
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        need = collections.defaultdict(int)
        window = collections.defaultdict(int)
        for c in s1:
            need[c] += 1

        left, right = 0, 0
        valid = 0

        while right < len(s2):
            cur = s2[right]
            right += 1

            if cur in need:
                window[cur] += 1
                if window[cur] == need[cur]:
                    valid += 1
            
            while right - left >= len(s1):
                if valid == len(need):
                    return True
                dele = s2[left]
                left += 1
                if dele in need:
                    if window[dele] == need[dele]:
                        valid -= 1
                    window[dele] -= 1
        return False
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        need = Counter(s1)
        wds = defaultdict(int)
        l, r = 0, 0
        valid = 0
        while r < len(s2):
            if s2[r] in need:
                wds[s2[r]] += 1
                if wds[s2[r]] == need[s2[r]]:
                    valid += 1
            r += 1
            
            if r > len(s1):
                delet_char = s2[l]
                l += 1
                if delet_char in need:
                    if wds[delet_char] == need[delet_char]:
                        valid -= 1
                    wds[delet_char] -= 1


            if r-l == len(s1):
                if valid == len(need):
                    return True

        

        return False