Leetcode 438. Find All Anagrams in a String

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

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/