438. Find All Anagrams in a String

解題思路

兩個 index 分別記錄出現次數，每次比對一不一樣。

滑動 window 的時候不用重新計算，而是以「拔掉 left」與「加上 right」的方式節省時間。

程式碼

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        int sArr[26] = {0}, pArr[26] = {0}, left = 0;
        if(p.size() > s.size()) return ans;

        for(int i=0; i<p.size(); i++)
        {
            pArr[p[i] - 'a']++;
            sArr[s[i] - 'a']++;
        }
        while(left <= s.size() - p.size())
        {
            bool isSame = true;
            for(int i=0; i<26; i++)
            {
                if(sArr[i] != pArr[i])
                    isSame = false;
            }
            if(isSame) ans.push_back(left);

            if(left == s.size() - p.size()) break;
            sArr[s[left] - 'a']--; sArr[s[left+p.size()] - 'a']++;
            left++;
        }
        return ans;
    }
};