class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
target = collections.Counter(p)
ans = []
for i in range(len(s)):
if i >= len(p):
target[s[i - len(p)]] += 1
if target[s[i - len(p)]] == 0:
del target[s[i - len(p)]]
target[s[i]] -= 1
if target[s[i]] == 0:
del target[s[i]]
if len(target) == 0:
ans.append(i - len(p) + 1)
return ans
你也可以将窗口封装成一个类进行操作。虽然代码会更长，但是如果你将窗口类看成黑盒，那么逻辑会很简单。
这里我提供一个 Python3 版本的封装类解法。
class FrequencyDict:
def __init__(self, s):
self.d = collections.Counter()
for char in s:
self.increment(char)
def _del_if_zero(self, char):
if self.d[char] == 0:
del self.d[char]
def is_empty(self):
return not self.d
def decrement(self, char):
self.d[char] -= 1
self._del_if_zero(char)
def increment(self, char):
self.d[char] += 1
self._del_if_zero(char)
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ans = []
freq = FrequencyDict(p)
for char in s[:len(p)]:
freq.decrement(char)
if freq.is_empty():
ans.append(0)
for i in range(len(p), len(s)):
start, end = s[i - len(p)], s[i]
freq.increment(start)
freq.decrement(end)
if freq.is_empty():
ans.append(i - len(p) + 1)
return ans
