3 ms prefix tree C++


  • 0
    C
    class MapSum {
    public:
        /** Initialize your data structure here. */
        struct Node {
            Node* children [26];
            int sum = 0;
            int val = 0;
            
            Node() {
                for (int i = 0; i < 26; i++) {
                    children[i] = NULL;
                }
            }
        };
        Node* root;
        MapSum() {
            root = new Node();
        }
        
        int util(Node* current, string& key, int ind, int val) {
            int diff = 0;
            if (!current->children[key[ind]-'a'])
                current->children[key[ind]-'a'] = new Node();
            current = current->children[key[ind]-'a'];
            
            if (ind == key.size()-1) {
                diff = val-current->val;
                current->val = val;
                current->sum += diff;
                return diff;
            }
    
            diff = util(current, key, ind+1, val);
            current->sum += diff;
            return diff;
        }
        void insert(string key, int val) {
            Node* current = root;
            util(root, key, 0, val);
        }
        
        int sum(string prefix) {
            Node* current = root;
            for (char c : prefix) {
                current = current->children[c-'a'];
                if (!current) return 0;
            }
            
            return current->sum;
        }
    };

Log in to reply
 

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