C++, 1 Set and 1 HashMap easy solution - O(1) sum


  • 0
    O

    class MapSum {
    public:

      void insert(string key, int val) {
        int oldval=m[key];
        for(int i=1;i<=key.size();i++){
            string str=key.substr(0,i);
            if(s.count(key))   { m[str]=m[str]-oldval+val; }
            else    {m[str]+=val;}
        }
        s.insert(key);
    }
    
    int sum(string prefix) { return m[prefix]; }
    

    private:

    unordered_set<string> s;
    unordered_map<string,int> m;
    

    };


Log in to reply
 

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