567. 字符串的排列-Medium.md

Description

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

 

示例 1：

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

示例 2：

输入: s1= "ab" s2 = "eidboaoo"
输出: False

提示：

• 输入的字符串只包含小写字母
• 两个字符串的长度都在 [1, 10,000] 之间

Solution

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        need, window = defaultdict(int), defaultdict(int)
        left, right = 0, 0
        valid = 0

        for i in s1:
            need[i] += 1

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

            # window moves right.
            if tmp_right in need:
                window[tmp_right] += 1
                if window[tmp_right] == need[tmp_right]:
                    valid += 1

            # window moves left.
            while valid == len(need):
                if right - left == len(s1):
                    return True

                tmp_left = s2[left]
                left += 1

                if tmp_left in need:
                    if window[tmp_left] == need[tmp_left]:
                        valid -= 1
                    window[tmp_left] -= 1

        return False