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);
 */