Leetcode 438. Find All Anagrams in a String

迈不过友情╰ 2022-09-09 00:13 75阅读 0赞

文章作者：Tyan  
博客：[noahsnail.com][] | [CSDN][] | [简书][Link 1]

## 1. Description ##

![Find All Anagrams in a String][]

## 2. Solution ##

\*\*解析：\*\*Version 1，判断两个字符串是否是Anagrams，可以采用字典的方法，即每个字母的个数及类型相等。先统计字符串`p`的字母个数并记录其长度在`stat`中，遍历字符串`s`，如果字母在`stat`中，则将其记录到字典`subs`中，否则重置`subs`，当`subs['length'] = stat['length']`时，比较二者是否相等，如果相等，则记录索引`index - n + 1`到结果列表中，此时字符串继续遍历，为保证`subs`长度与`stat`长度一致，此时，`subs`中移除`s[index - n + 1]`字符，同时长度减`1`。

*  Version 1

class Solution:
        def findAnagrams(self, s: str, p: str) -> List[int]:
            stat = collections.Counter(p)
            n = len(p)
            stat['length'] = n
            result = []
            subs = collections.defaultdict(int)
            for index, ch in enumerate(s):
                if ch in stat:
                    subs[ch] += 1
                    subs['length'] += 1
                else:
                    subs = collections.defaultdict(int)
                    continue
                if subs['length'] == stat['length']:
                    if stat == subs:
                        result.append(index - n + 1)
                    subs[s[index - n + 1]] -= 1
                    subs['length'] -= 1
            return result

## Reference ##

1.  [https://leetcode.com/problems/find-all-anagrams-in-a-string/][https_leetcode.com_problems_find-all-anagrams-in-a-string]

[noahsnail.com]: http://noahsnail.com
[CSDN]: http://blog.csdn.net/quincuntial
[Link 1]: http://www.jianshu.com/users/7731e83f3a4e/latest_articles
[Find All Anagrams in a String]: /images/20220829/f792605dabf2449c83d42d81b1951e8e.png
[https_leetcode.com_problems_find-all-anagrams-in-a-string]: https://leetcode.com/problems/find-all-anagrams-in-a-string/