unordered_map Solution C++ 36ms


  • 0
    N
    vector<int> findAnagrams(string s, string p) {
        vector<int> returnValues;
    
        // none of these work
        if(p.empty() || s.empty() || p.length() > s.length()) {
            return returnValues;
        }
    
        // hold onto the orignal to make reseting quick and easy
        unordered_map<char, int> anagramMapOG;
        unordered_map<char, int> anagramMap;
        int anagramCounter = p.size();
    
        for (int i = 0; i < anagramCounter; i++) {
            // we only need to know how many there are
            anagramMap[p[i]]++;
            anagramMapOG[p[i]]++;
        }
    
        for (int i = 0; i < s.size(); i++) {
            // auto makes life nice
            auto findIter = anagramMap.find(s[i]);
    
            if (findIter != anagramMap.end()) {
                // if it was found and there is room for it
                if (findIter->second > 0) {
                    anagramCounter--;
                    findIter->second--;
                }
                else {
                    // no bueno, a little clean up is needed now
                    // need to jump ahead as we hit too many of the same
                    for (int j = (p.size() - anagramCounter); j > 0; j--) {
                        char tempIndex = s[i-j];
    
                        if (tempIndex == s[i]) {
                            anagramCounter = (p.size() - j);
                            break;
                        }
                        // remove them!
                        anagramMap[tempIndex]++;
                    }
                }
            }
            else {
                // it just was not found
                // so everything needs to be reset
                if (anagramCounter != p.size()) {
                    anagramCounter = p.size();
                    anagramMap = anagramMapOG;
                }
            }
    
            // got um!
            if (anagramCounter == 0) {
                anagramCounter++;
                anagramMap[s[i - (p.size()-1)]]++;
                returnValues.push_back(i - (p.size()-1));
            }
        }
    
        return returnValues;
    }
    

Log in to reply
 

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