C++ 32ms sliding window super concise


  • 0
    Z
        vector<int> findAnagrams(string s, string p) {
            if (s.empty() || s.length() < p.length()) return vector<int>();
            int slen = s.length(), plen = p.length(), k = 0;
            vector<int> pmap(26, 0), smap, res;
            
            for (char c : p) ++pmap[c - 'a'];
            smap = pmap; //pmap is the hashmap for string p, smap is the copy we work on
            for (int i = 0; i < slen; ++i) {
                if (pmap[s[i] - 'a'] == 0) { //char not existed in string p, reset smap and sliding window
                    smap = pmap;
                    k = 0;
                } else {
                    ++k; 
                    --smap[s[i] - 'a'];
                    //whenever we got an extra char, shrink the sliding window until that extra char being removed
                    while (smap[s[i] - 'a'] < 0)
                        ++smap[s[i - k-- + 1] - 'a'];
    
                    if (k == plen) { // sliding window size equal to length of p
                        res.push_back(i - plen + 1);
                        ++smap[s[i - k-- + 1] - 'a'];
                    }
                }
            }
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.