python力扣438.找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释: 起始索引等于 0 的子串是 “cba”, 它是"abc" 的异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

示例 2:

输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释: 起始索引等于 0 的子串是 “ab”, 它是 “ab”
的异位词。 起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。 起始索引等于 2 的子串是 “ab”, 它是 “ab”
的异位词。

提示:

1 <= s.length, p.length <= 3 * 104 s 和 p 仅包含小写字母

我最开始用的排序来确定两个字符串是否相等，但在一些长的字符串上就没有那么好用。所以使用这个：collections.Counter这个操作可以返回一个字典，存储对象的出现频率。比如 p = “aabb”，那么 Counter（p）的结果是一个字典：Counter({‘a’: 2, ‘b’: 2})。

大体思路如下：使用一个先加后减的原则，首先初始化滑动窗口（从0到n-1）的字符频率为一个字典，然后从n-1开始遍历，先添加当前字符到字典中，如果该字典与p的频率字典相等，可判定为是异位词的子串，将1-n+1添加到结果列表中（目前的i是指向滑动窗口结尾的，需要减掉滑动窗口的长度），不管是否如此，都需要移除左边的字符，然后在下一次循环的时候加入右边新的字符。
另外：如果频率等于0，要注意移除key，不然字典会对应不上。

后来知道，这个思想叫滑动窗口。

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        from collections import Counter

        p_count = Counter(p)
        n = len(p)
        ans = []

        window_count = Counter(s[:n - 1])

        for i in range(n - 1, len(s)):
            window_count[s[i]] += 1
            if window_count == p_count:
                ans.append(i - n + 1)
            window_count[s[i - n + 1]] -= 1
            if window_count[s[i - n + 1]] == 0:
                del window_count[s[i - n + 1]]

        return ans