677 Map Sum Pairs

677.Map Sum Pairs

1. Question

Implement a MapSum class withinsert, andsummethods.

For the methodinsert, 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 methodsum, 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

2. Implementation

(1) Trie

class MapSum {
    class TrieNode {
        char val;
        int sum;
        boolean isWord;
        TrieNode[] childNode;

        public TrieNode(char val, int sum) {
            this.val = val;
            this.sum = sum;
            childNode = new TrieNode[256];
        }
    }

    class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode(' ', 0);
        }

        public void insert(String word, int sum, boolean overridden) {
            if (word == null || word.length() == 0) {
                return;
            }

            TrieNode curNode = root;

            for (char c : word.toCharArray()) {
                if (curNode.childNode[c] == null) {
                    curNode.childNode[c] = new TrieNode(c, sum);
                }
                else {
                    curNode.childNode[c].sum = overridden ? sum : curNode.childNode[c].sum + sum;
                }
                curNode = curNode.childNode[c];
            }
            curNode.isWord = true;
        }

        public int searchByPrefix(String prefix) {
            if (prefix == null || prefix.length() == 0) {
                return 0;
            }

            TrieNode curNode = root;

            for (char c: prefix.toCharArray()) {
                if (curNode.childNode[c] == null) {
                    return 0;
                }
                curNode = curNode.childNode[c];
            }
            return curNode.sum;
        }
    }
    Set<String> set;
    Trie trie;

    /** Initialize your data structure here. */
    public MapSum() {
        set = new HashSet();
        trie = new Trie();
    }

    public void insert(String key, int val) {
        trie.insert(key, val, !set.add(key));
    }

    public int sum(String prefix) {
        return trie.searchByPrefix(prefix);
    }
}

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

3. Time & Space Complexity

Trie: insert(): 时间复杂度O(L),L为insert的word的长度, sum(): 时间复杂度O(n)，n 为输入的prefix的长度，空间复杂度: O(m), m为插入insert的word的个数