leetcode 438. Find All Anagrams in a String 滑动窗口法

╰半夏微凉° 2022-05-26 07:07 143阅读 0赞

[题目链接][Link 1]  
![这里写图片描述][70]

## 解析 ##

主要使用滑动窗口法解题，需要好好体会的是中间的两个判断couter的用法，这里很巧妙。  
如果想了解更多的滑动窗口法内容，看这里：  
[滑动窗口法详解][Link 2]

## 代码 ##

from collections import defaultdict
    
    class Solution:
        def findAnagrams(self, s, p):
            """ :type s: str :type p: str :rtype: List[int] """
            res = []
            map_dict = defaultdict(int)
            if len(p) > len(s):
                return res
            for c in p:
                map_dict[c] += 1
            couter = len(map_dict)
            begin, end = 0, 0
    
            while end < len(s):
                c = s[end]
                if c in map_dict:
                    map_dict[c] -= 1
                    # 与下面的判断，每遇到一个在map_dict中的字符就减1，下面的判断每次遇到一个在map_dict字符就加1
                    if map_dict[c] == 0:
                        couter -= 1
                end += 1
    
                while couter == 0:
                    tempc = s[begin]
                    if tempc in map_dict:
                        map_dict[tempc] += 1
                        # 为了下次找到再出现的map_dict中的数
                        if map_dict[tempc] > 0:
                            couter += 1
                    if len(p) == end - begin:
                        res.append(begin)
                    begin += 1
            return res

[Link 1]: https://leetcode.com/problems/find-all-anagrams-in-a-string/description/
[70]: /images/20220526/c2ae68dbf1da4c48bf0804060836c325.png
[Link 2]: https://blog.csdn.net/sty945/article/details/79846516