438 找到字符串中的所有字母异位词
推荐写法
字母异位词和排列的意思一模一样,参考567 字符串的排列
唯一不同的是记录起始索引,只需要返回结果的时候,把返回true改为记录起始索引
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
unordered_map<char, int> window, need;
vector<int> ans;
for(char c: p){
need[c]++;
}
int left = 0, right = 0;
int valid = 0;
while(right < s.size()){
char c = s[right];
right++;
if(need.count(c)){
window[c]++;
if(window[c] == need[c]){
valid++;
}
}
while(right - left >= p.size()){
if(valid == need.size()){
ans.push_back(left);
}
char d = s[left];
left++;
if(need.count(d)){
if(window[d] == need[d]){
valid--;
}
window[d]--;
}
}
}
return ans;
}
};