C++ sliding window solution with unordered_map


  • 0
    C

    This solution is pretty much similar with this one. Instead of vector, I use unordered_map to keep track of sliding window string.

    class Solution {
    public:
        vector<int> findAnagrams(string s, string p) {
            vector<int> res;
            if (s.size() < p.size()) return res;
            unordered_map<char, int> m_p, m_s;
            for (int i = 0; i < 256; i++) {
                m_p[char(i)] = 0;
                m_s[char(i)] = 0;
            }
            for (int i = 0; i < p.size(); i++) {
                m_p[p[i]] ++;
                m_s[s[i]] ++;
            }
            if (m_p == m_s) res.push_back(0);
            for (int i = p.size(); i < s.size(); i++) {
                m_s[s[i]] ++;
                m_s[s[i - p.size()]] --;
                if (m_s == m_p) res.push_back(i - p.size() + 1);
            }
            return res;
        }
    };
    

    This solution is much slower than using vectors. Someone who could show me why is very welcome to discuss.


Log in to reply
 

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