【算法竞赛刷题模板16】滑动窗口

• 滑动窗口专练
• python中字典是可变对象，所以可以直接根据键值对修改
• 博客来源： LawsonAbs@CSDN

变位词指的就是一个词中的字符位置变了，但是各个字符出现的次数没有改变。例如：abc和cba这两个词就互称变位词。

（1）有什么快捷的方法可以判断二者是否互为变位词？
如果二者对于所有的词数目是一样的话，那么就互为变为词

from collections import Counter

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        window = len(p) # p的长度就是滑动窗口的大小
        res = []
        # 不仅需要考虑字符是否出现过，还需要考虑字符出现的频率
        for left in range(len(s)-window+1):
            right =  left + window
            span = s[left:right] # 得到窗口的内容
            
            if self.is_true(span,p):
                res.append(left)
        return res
    
    # 使用一个Counter来判断二者是否为变位词，但是这个时间复杂度会很高，导致过不完测试样例
    def is_true(self,span,p):
        if Counter(span) == Counter(p):
            return True
        return False

上述方法本是为了偷懒，但是哪知道在新建对象的时候会有如此耗时间，所以将代码修改（主要是不针对每个span都新建一个Counter对象，而是在原来的基础上进行修改）如下：

from collections import Counter
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        window = len(p) # p的长度就是滑动窗口的大小
        res = []
        cnt = Counter(s[:window-1]) # 得到一个基本的计数信息
        stad = Counter(p)
        # 不仅需要考虑字符是否出现过，还需要考虑字符出现的频率
        for left in range(len(s)-window+1):
            right =  left + window
            # span = s[left:right] # 得到窗口的内容
            cnt[s[right-1]] += 1
            # print("cnt=",cnt)
            if cnt == stad:
                res.append(left)
            
            cnt[s[left]] -= 1
        return res

~