C++ trie bfs solution 3ms


  • 0
    J
    class TrieNode
    {
    public:
        unordered_map<char, TrieNode*> children;
        int val;
        TrieNode(): val(0){};
    };
    class MapSum {
    public:
        TrieNode* root;
        void insertTrie(string key, int val)
        {
            TrieNode* cur = root;
            for(char c: key)
            {
                if(cur && !cur->children.count(c))
                    cur->children[c] = new TrieNode;
                cur = cur->children[c];
            }
            cur->val = val;
        }
        
        void dfs(TrieNode* root, int& sum)
        {
            for(auto elem : root->children)
            {
                sum+=elem.second->val;
                dfs(elem.second, sum);
            }
        }
        
        
    public:
        /** Initialize your data structure here. */
        MapSum() {
            root = new TrieNode;
        }
        
        void insert(string key, int val) {
            insertTrie(key, val);
        }
        
        int sum(string prefix) {
            TrieNode* cur = root;
            for(char c: prefix)
            {
                if(cur && !cur->children.count(c))
                    return 0;
                cur = cur->children[c];
            }
            int summer = cur->val;
            dfs(cur, summer);
            return summer;
        }
    };
    
    /**
     * Your MapSum object will be instantiated and called as such:
     * MapSum obj = new MapSum();
     * obj.insert(key,val);
     * int param_2 = obj.sum(prefix);
     */
    

Log in to reply
 

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