677. Map Sum Pairs

Problem:

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

Analysis:
Solution 1 DFS:
这道题trie的方法是我自己想出来的。store val to TrieNode, from prefix use DFS go down and sum up. Leetcode discussion 里面谷歌大神的实现太牛逼了，原来DFS还可以这样玩。

class MapSum {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        int val;
    }
    TrieNode root;
    /** Initialize your data structure here. */
    public MapSum() {
        root = new TrieNode();
    }
    
    public void insert(String key, int val) {
        TrieNode node = root;
        for (char c: key.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.val = val;
    }
    
    public int sum(String prefix) {
        TrieNode node = root;
        for (char c: prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return 0;
            }
            node = node.children[index];
        }
        return dfs(node);
    }
    
    private int dfs(TrieNode node) {
        int sum = 0;
        for (TrieNode n: node.children) {
            if (n != null) {
                sum += dfs(n);
            }
        }
        return sum + node.val;
    }
}

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

Solution 2:

一开始思路想到了，但是知道怎么实现，所以改用dfs的方法。Two maps, one stores the word and val, the other stores prefix sum. If the word exist, update prefix sum with diff.

class MapSum {
    Map<String, Integer> wordMap = new HashMap<>();
    Map<String, Integer> preMap = new HashMap<>();
    /** Initialize your data structure here. */
    public MapSum() {
        
    }
    
    public void insert(String key, int val) {
        int diff = val - wordMap.getOrDefault(key, 0);
        // build prefix map
        String s = "";
        for (char c: key.toCharArray()) {
            s += c;
            preMap.put(s, preMap.getOrDefault(s, 0) + diff);
        }
        wordMap.put(key, val);
    }
    
    public int sum(String prefix) {
        return preMap.getOrDefault(prefix, 0);
    }
}

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