677. Map Sum Pairs.md

677. Map Sum Pairs

Question:

Implement a MapSum class with insert, and sum methods.

For the method insert, you'll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix.

Example 1:

Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5

Solution

• Method 1: Trie Tree

class MapSum {

    private static class Node{
        int count;
        Node[] childs;
        boolean isLeaf;
        public Node(){
            this.childs = new Node[26];
        }
    }
    private Node root;
    /** Initialize your data structure here. */
    public MapSum() {
        this.root = new Node();
    }

    public void insert(String key, int val) {
        char[] arr = key.toCharArray();
        Node node = root;
        for(int i = 0; i < arr.length; i++){
            int c = arr[i] - 'a';
            if(node.childs[c] == null){
                node.childs[c] = new Node();
            }
            node = node.childs[c];
        }
        node.isLeaf = true;
        node.count = val;
    }

    public int sum(String prefix) {
        char[] arr = prefix.toCharArray();
        Node node = root;
        for(int i = 0; i < arr.length; i++){
            int c = arr[i] - 'a';
            if(node.childs[c] == null){
                return 0;
            }else{
                node = node.childs[c];
            }
        }
        return childsCount(node);
    }
    private int childsCount(Node node){
        int count = node.count;
        for(int i = 0; i < 26; i++){
            if(node.childs[i] != null){
                count += childsCount(node.childs[i]);
            }
        }
        return count;
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */

C++ Version

class MapSum {
public:
    /** Initialize your data structure here. */
    MapSum() {
        root_.reset(new Node());
    }
    void insert(string key, int val) {
        Node* temp = root_.get();
        Node* test = contains(key);
        int diff = (test && test->isLeaf) ? val - test->sum: val;
        temp->sum += diff;
        for(const char & c: key){
            if(!temp->childs[c - 'a']){
                temp->childs[c - 'a'] = new Node();
            }
            temp = temp->childs[c - 'a'];
            temp->sum += diff;
        }
        temp->isLeaf = true;
    }
    int sum(string prefix) {
        Node* temp = root_.get();
        for(const char & c: prefix){
            if(!temp->childs[c - 'a']) return 0;
            temp = temp->childs[c - 'a'];
        }
        return temp->sum;
    }
private:
    struct Node{
        vector<Node*> childs;
        int sum;
        bool isLeaf;
        Node(): childs(26, nullptr), sum(0), isLeaf(false){};
        ~Node(){
            for(auto node: childs){
                delete node;
            }
        }
    };
    Node* contains(string word){
        Node * temp = root_.get();
        for(const char & c: word){
            if(!temp->childs[c - 'a']) return nullptr;
            temp = temp->childs[c - 'a'];
        }
        return temp;
    }
    unique_ptr<Node> root_;
};
/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum* obj = new MapSum();
 * obj->insert(key,val);
 * int param_2 = obj->sum(prefix);
 */