C++ multiset solution


  • 0
    F
    class Solution {
    public:
        vector<int> findAnagrams(string s, string p) {
            vector<int> res;
            const int len = p.size();
            
            if (s.size() < len) {
                return res;
            }
            
            multiset<char> pms(p.begin(), p.end());
            multiset<char> sms(s.begin(), s.begin() + len);
            multiset<char> missing;
            multiset<char> surplus;
            
            set_difference(pms.begin(), pms.end(), sms.begin(), sms.end(), inserter(missing, missing.begin()));
            set_difference(sms.begin(), sms.end(), pms.begin(), pms.end(), inserter(surplus, surplus.begin()));
            
            int i = 0;
            while(true) {
                if (missing.empty()) {
                    res.push_back(i);
                }
                
                // reach the end
                if (i + len == s.size()) {
                    break;
                }
                
                // delete the old char
                auto d = surplus.find(s[i]);
                if (d != surplus.end()) {
                    surplus.erase(d);
                } else {
                    missing.insert(s[i]);
                }
                
                // add the new char
                auto n = missing.find(s[i + len]);
                if (n != missing.end()) {
                    missing.erase(n);
                } else {
                    surplus.insert(s[i+len]);
                }
                
                i++;
            }
            
            return res;
        }
    };
    

Log in to reply
 

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