[677. Map Sum Pairs] C++_Prefix Tree


  • 0

    Very straightforward solution.

    class TrieNode{
    public:
    TrieNode(){
        children.resize(26);
    }
    vector<TrieNode*> children;
    unordered_map<string, int> mp;
    };
    
    class MapSum {
    public:
    /** Initialize your data structure here. */
    TrieNode* root;
    MapSum() {
        root = new TrieNode();
    }
    
    void insert(string key, int val) {
        TrieNode* node = root;
        for(int i = 0; i < key.size(); ++i){
            int pos = key[i] - 'a';
            if(node->children[pos] == nullptr){
                TrieNode* temp = new TrieNode();
                node->children[pos] = temp;
            }
            node->mp[key] = val;
            node = node->children[pos];
        }
        node->mp[key] = val;// Do not forget
    }
    
    int sum(string prefix) {
        TrieNode* node = root;
        int sum = 0;
        for(int i = 0; i < prefix.size(); ++i){
            if(node == nullptr) break;
            node = node->children[prefix[i] - 'a'];
        }
        if(node == nullptr) return 0;
        for(auto m : (node->mp)){
            sum += m.second;
        }
        return sum;
    }
    };

Log in to reply
 

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