题目描述

在s中找p的anagram

样例

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

算法1

滑动窗口法 $O(n)$

C++ 代码

    // sliding window problem
    // 用hashtable 记录 p 中的字符个数，用 total 记录 p 中unique char的个数
    // 左右指针 i，j，前进 j，并 hash[s[j]]--；如果减到0，seen++
    // 当 j-i+1 超过p的长度时，前进 i，更新 hashtable和seen
    // 如果seen == total，记录一个解

    vector<int> findAnagrams(string s, string p) {
        if(p.size()==0) return vector<int>();

        unordered_map<char, int> hash;
        for(auto c : p) hash[c]++;

        vector<int> res;

        int total = hash.size();
        int seen = 0;
        for(int i=0, j=0; j<s.size(); j++) {
            hash[s[j]]--;

            if(hash[s[j]]==0) seen++;

            // move i
            while(j-i+1 > p.size()) {
                hash[s[i]] ++;
                if(hash[s[i]]==1) seen--;
                i++;
            }

            if(seen == total) res.push_back(i);
        }

        return res;
    }