Description:
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example:
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".
Link:
https://leetcode.com/problems/find-all-anagrams-in-a-string/#/description
解题方法：
用字符的分布来匹配anagrams，用slide window来优化暴力算法。当i>p的长度时，每次i++都相当于窗口右移动。左边需要减去刚刚划过的记录。
Tips:
不能用unordered_map来当哈希表。
Time Complexity：
O(n)
完整代码：
vector<int> findAnagrams(string s, string p)
{
vector<int> result;
int lenp = p.size();
int lens = s.size();
if(s.size() == 0 || p.size() > s.size())
return result;
vector<int> hash1(26);
vector<int> hash2(26);
for(auto a: p)
hash1[a-'a']++;
for(int i = 0; i < s.size(); i++)
{
hash2[s[i]-'a']++;
if(i >= lenp) hash2[s[i-lenp]-'a']--; //加上右边的记录，减去左边的记录
if(hash1 == hash2) result.push_back(i-lenp+1);
}
return result;
}
