題目： LeetCode - 438. Find All Anagrams in a String

題目說明

給兩個 String s、p，求 s 中某段文字結構組成和 p 相同的 index。

解題思路

建兩個表，vp 放 p 中的英文字母個數，vs 放 s 某段的英文字母個數。使用一個迴圈遍歷 s，將遍歷到的元素加入 vs，當裡面存放的字母個數超過 p 的長度時，需要把最前面的刪除。最後判斷 vs 是否等於 vp 即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int ls = s.size(), lp = p.size();
        vector<int> vs(26), vp(26), res;
        for(auto c : p)
            ++vp[c - 'a'];
        for(int i = 0; i < ls; ++i)
        {
            if(i >= lp)
                --vs[s[i - lp] - 'a'];
            ++vs[s[i] - 'a'];
            if(vs == vp)
                res.push_back(i - lp + 1);
        }
        return res;
    }
};