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來優(yōu)化暴力算法定躏。當(dāng)i>p的長度時祠斧，每次i++都相當(dāng)于窗口右移動梭伐。左邊需要減去剛剛劃過的記錄念搬。
Tips:
不能用unordered_map來當(dāng)哈希表奕扣。
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;
}
