438 - Find All Anagrams in a String

解法一 - Sliding Window

這題的解法概念跟 # 567 基本上一樣,差別只在找到一個 permutation 就把 windowStart 加入答案中,實作如下:

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> table;
        for(auto c:p)
            table[c]++;

        vector<int> res;
        int windowStart = 0, matched = 0;
        for(int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char endChar = s[windowEnd];

            if(table.find(endChar) != table.end()) {
                table[endChar]--;
                if(table[endChar] == 0) {
                    matched++;
                }
            }

            if(windowEnd - windowStart + 1 > p.length()) {
                char startChar = s[windowStart++];
                if(table.find(startChar) != table.end()) {
                    if(table[startChar] == 0)
                        matched--;
                    table[startChar]++;
                }
            }

            // Note that this equals to table.size()
            // instead of s1.legnth() because there might be duplicate chars in s1
            if(matched == table.size())
                res.push_back(windowStart);
        }

        return res;   
    }
};

results matching ""

    No results matching ""