跳转至

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;
    }
};