C++11 Trie and Map solutions


  • 0

    Map solution:
    Using a map, simply insert key/val pairs. When calculating the sum, start iterating through the map at the lower_bound() of the prefix. This lower_bound() string key is either equal to prefix, or alphabetically ordered just after the prefix. Add up the sum by continuing to iterate through the map while the beginning of the key equals the prefix.

    class MapSum {
    public:
        /** Initialize your data structure here. */
        MapSum() : _map{} {}
        
        void insert(string key, int val) {
            _map[key]=val;
        }
        
        int sum(string prefix) {
            int cnt=0, sz=(int)prefix.size();
            map<string,int>::iterator itr;
            for (itr=_map.lower_bound(prefix); itr!=_map.end(); itr++){
                if (itr->first.substr(0,sz)==prefix){ cnt+=itr->second; } else { break; }
            }
            return cnt;
        }
    private:
        map<string,int> _map;
    };
    

    Trie solution:
    Using a trie + unordered_map, for each character in the trie, store an unordered_map of keys which are included under this character.

    For example, if "apple" is inserted with value 3, then the trie looks like this:

    a ==> dic["apple"]=3
    p ==> dic["apple"]=3
    p ==> dic["apple"]=3
    l ==> dic["apple"]=3
    e ==> dic["apple"]=3
    

    Then if "app" is inserted with value 2, then the trie looks like this:

    a ==> dic["apple"]=3, dic["app"]=2
    p ==> dic["apple"]=3, dic["app"]=2
    p ==> dic["apple"]=3, dic["app"]=2
    l ==> dic["apple"]=3
    e ==> dic["apple"]=3
    
    class TrieNode{
    public:
        unordered_map<string,int> dic;
        vector<shared_ptr<TrieNode>> next;
        TrieNode(string key, int val) : next{26,nullptr} {
            dic[key]=val;
        }
    };
    
    class MapSum {
    public:
        /** Initialize your data structure here. */
        MapSum() : _root{make_shared<TrieNode>("",0)} {}
        
        void insert(string key, int val) {
            int idx=0;
            auto curr=_root;
            transform(key.begin(), key.end(), key.begin(), ::tolower);
            for (auto& ch : key){
                idx=ch-'a';
                if (!curr->next[idx]){
                    curr->next[idx]=make_shared<TrieNode>(key,val);
                } else {
                    curr->next[idx]->dic[key]=val;
                }
                curr=curr->next[idx];
            }
        }
        
        int sum(string prefix) {
            int res=0;
            auto curr=_root;
            for (auto& ch : prefix){
                int idx=ch-'a';
                if (curr->next[idx]){
                    curr=curr->next[idx];
                } else {
                    return 0;
                }
            }
            for (auto& item : curr->dic){
                res+=item.second;
            }
            return res;
        }
        
    private:
        shared_ptr<TrieNode> _root;
    };
    

Log in to reply
 

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