567. 字符串的排列

567. 字符串的排列

给你两个字符串 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 <= 104
• s1 和 s2 仅包含小写字母

class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        window = {}
        needs = dict((i, s1.count(i)) for i in s1)
        left = 0
        right = 0

        valid = 0
        while right < len(s2):
            c1 = s2[right]
            right += 1

            if c1 in needs.keys():
                window[c1] = window.get(c1, 0) + 1
                if window[c1] == needs[c1]:
                    valid += 1
            
            while valid == len(needs):

                if right - left == len(s1):
                    return True
                
                c2 = s2[left]
                left += 1
                if c2 in needs.keys():
                    window[c2] -= 1
                    if window[c2] < needs[c2]:
                        valid -= 1
                        
        return False