problem
438. Find All Anagrams in a String
solution1:
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
if(s.empty()) return {};
vector<int> res, pv(, );
for(auto a:p) pv[a]++;
int sn = s.size();
int i = ;
while(i<sn)
{
vector<int> tmp = pv;
bool is = true;
for(int j=i; j<i+p.size(); j++)
{
if(--tmp[s[j]]<)
{
is = false;
break;
}
}
if(is) res.push_back(i);
i++;
}
return res;
}
};
solution2:使用哈希表表示一定字符长度内各个字符的个数，每次滑窗需要添加最新的字符，且减去最旧的字符，然后比较哈希表。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
if(s.empty()) return{};
vector<int> res, m1(, ), m2(, );
for(int i=; i<p.size(); i++)
{
m1[p[i]]++;
m2[s[i]]++;
}
if(m1==m2) res.push_back();
for(int i=p.size(); i<s.size(); i++)
{
m2[s[i]]++;
m2[s[i-p.size()]]--;
if(m1==m2) res.push_back(i-p.size()+);
}
return res;
}
};
参考
1. Leetcode_438. Find All Anagrams in a String;
完