[567][中等][滑动窗口] 字符串的排列

题目描述

567. 字符串的排列

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

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

示例1:

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

示例2:

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

注意：

• 输入的字符串只包含小写字母

• 两个字符串的长度都在 [1, 10,000] 之间

解题思路

同[438][中等][滑动窗口] 找到字符串中所有字母异位词, 简化版本.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        n, num_total = len(s2), len(s1)
        mapping = Counter(s1)

        s_map, s_count = dict(), 0
        res = []
        left = right = 0
        while right < n:
            char = s2[right]
            right += 1

            if char not in mapping:
                s_map.clear()
                s_count = 0
                left = right
            else:
                count = s_map.get(char, 0)
                s_map[char] = count + 1
                if count < mapping[char]:
                    s_count += 1

                while right - left == num_total:
                    if s_count == num_total:
                        return True
                    char = s2[left]
                    left += 1
                    count = s_map.get(char, 0)
                    s_map[char] = count - 1
                    if count <= mapping[char]:
                        s_count -= 1
        return False