建立目标string的char to count map
简历window的char to count map
使用一个count变量来计算window中后多少个char符合要求
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
charFreq = {} # target charFreq Map
for c in p:
charFreq[c] = charFreq.get(c, 0) + 1
windows = {} # keep track of chars in windows
res = []
count = 0
i, j = 0, 0
while j < len(s):
if s[j] in charFreq:
windows[s[j]] = windows.get(s[j], 0) + 1
if windows[s[j]] <= charFreq[s[j]]: # windows need this char
count += 1
j += 1 # increase j, extend window
if j - i == len(p): # window is full
if count == len(p):
res.append(i)
if s[i] in charFreq:
if windows[s[i]] <= charFreq[s[i]]: # windows don't need this char
count -= 1
windows[s[i]] -= 1
i += 1 # increase i, move window
return res
e438 Find All Anagrams in a String
e219 Contains Duplicate II
