Given two strings
s and p, return an array of all the start indices of p‘s anagrams in s. You may return the answer in any order.An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = “cbaebabacd”, p = “abc”
Output: [0,6]
Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Example 2:
Input: s = “abab”, p = “ab”
Output: [0,1,2]
Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.
Constraints:
`1 <= s.length, p.length <= 3 104
*sandp` consist of lowercase English letters.题目大意：
求字符串s中含p的anagram的所有初始下标
解题思路：
求某子串的频率统计，第一时间想到滑动窗口。此题较特殊，属于固定大小窗口的滑动窗口，因为p的大小是固定的，窗口大小必须和p长度一样。
解题步骤：
N/A
注意事项：
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14def findAnagrams(self, s: str, p: str) -> List[int]:
char_to_count_p = collections.Counter(p)
substr_win = collections.defaultdict(int)
res = []
for i, char in enumerate(s):
substr_win[s[i]] += 1
# window: [i - len(p) + 1, i]
if i >= len(p):
substr_win[s[i - len(p)]] -= 1
if substr_win[s[i - len(p)]] == 0:
substr_win.pop(s[i - len(p)])
if substr_win == char_to_count_p:
res.append(i - len(p) + 1)
return res
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
