[数据结构与算法]python leetcode 567 字符串的排列【中等题】

一 读懂题目

二.?分析，推导解法，产生思路。

解题思路：

转化：排列 => 两个字符串中每个字符出现的次数均相等; => 关注字符种数与次数

s1的长度即为滑动窗口大小。暴力解法：遍历s2,维持一个固定大小滑动窗口，比较s2窗口子串与s1字符串对应字符及次数是否相同。

优化方法：注意短子串存在目标子串，则长子串（在短子串前后加字符形成的长子串）也包含目标子串。

三 代码实现

注意：

winCount 的含义：滑动窗口中的字符要满足字符出现的次数 大于等于 s1 中对应字符出现的次数的时候才加1，
winCount 不仅统计了种类，还代表了次数。使得我们可以通过 winCount 的数值去了解整个滑动窗口的信息。

dict_s1 ={}
        dict_s2 = {}

        for i in range(len(s1)):
            if s1[i] not in dict_s1:
                dict_s1[s1[i]] = 1
            else:
                dict_s1[s1[i]] += 1
            
        pCount = len(dict_s1)   # 计算s1中字符出现的次数
        winCount = 0

        # 遍历S2
        right = 0
        left = 0
        while right < len(s2):
            # 右指针
            # 计算dict_s2的字符及次数
            if s2[right] not in dict_s2:
                dict_s2[s2[right]] = 1
            else:
                dict_s2[s2[right]] +=1
            # 判断s2中是否存在与s1，字符及次数相同的情况
            if s2[right] in dict_s1:    # 先判断s1中是否存在字符s2[right]
                if dict_s2[s2[right]] == dict_s1[s2[right]]:    # 判断字符s2[right]在两个子串中出现次数是否相同
                    winCount += 1
            right += 1  # 右指针右移

            # 左指针:当当前子串含有目标子串（s1）时，左指针才右移
            while pCount == winCount:
                if right - left == len(s1): # 当前子串与固定窗口一样大，则找到目标子串
                    return True
                # 当前子串与固定窗口一样大, 移动左指针
                if s2[left] in dict_s1:
                    dict_s2[s2[left]] -= 1
                    if dict_s2[s2[left]] < dict_s1[s2[left]]:
                        winCount -= 1   # 当前子串不含有目标子串，左指针停止右移，右指针再次右移
                left += 1

        return False

?

?