给出两个字符串p和s,问p的某种排列是否是s的子串,如果存在,输出所有匹配的位置。类似第567题(http://www.cppblog.com/Uriel/articles/229660.html)
先用Counter计算p各个字符的出现次数,然后用sliding window,s出现在sliding window中的字符对应的Counter减1,发现某位置sliding window让Counter中所有计数归零时记录位置
1 #438
2 #Runtime: 371 ms (Beats 12.21%)
3 #Memory: 14.6 MB (Beats 29.63%)
4
5 class Solution(object):
6 def findAnagrams(self, s, p):
7 """
8 :type s: str
9 :type p: str
10 :rtype: List[int]
11 """
12 cnt_p = Counter(p)
13 l = len(p)
14 ans = []
15 for i in range(len(s)):
16 if s[i] in cnt_p:
17 cnt_p[s[i]] -= 1
18 if i >= l and s[i-l] in cnt_p:
19 cnt_p[s[i-l]] += 1
20 if all([cnt_p[j] == 0 for j in cnt_p]):
21 ans.append(i - l + 1)
22 return ans