438.Find All Anagrams in a String
题目描述:
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.
给定一个字符串s和一个非空字符串p，在s中查找p的变位词的所有起始索引。字符串仅由小写英文字母组成，字符串s和p的长度将不大于20,100。输出顺序无关紧要。
思路
一开始，我只当是字符串匹配来做了，做出来发现最后一个超时，又加了KMP，还是超时。后来也有了想法，只是花太多时间了，就没有再去写，于是参考大神的解法。
代码
//解法1(没有AC，并且考虑不周全)：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int n = s.size();
int m = p.size();
vector<int> res;
unordered_set<char> dict;
for(auto e : p)
dict.insert(e);
sort(p.begin(), p.end());
for(int i = 0; i <= n-m; ++i){
string tmp = s.substr(i,m);
//cout << tmp << endl;
int j = 0;
for(; j < m; ++j){
if(dict.find(tmp[j]) == dict.end()){
break;
}
}
sort(tmp.begin(), tmp.end());
if(j == m){
if(p == tmp){
res.push_back(i);
}
}else{
i += j;
}
}
return res;
}
};
//解法2(滑动窗口)：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> pv(26,0), sv(26,0), res;
if(s.size() < p.size())
return res;
for(int i = 0; i < p.size(); ++i)
{
++pv[p[i]-'a'];
++sv[s[i]-'a'];
}
if(pv == sv)
res.push_back(0);
for(int i = p.size(); i < s.size(); ++i)
{
++sv[s[i]-'a'];
--sv[s[i-p.size()]-'a'];
if(pv == sv)
res.push_back(i-p.size()+1);
}
return res;
}
};
