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

这题我取巧了，用了startWith。时间
insert: O(1)
sum: O(n * len(key)) 每次都要遍历所有key

    Map<String, Integer> map;

    public MapSum() {
        map = new HashMap<String, Integer>();
    }

    public void insert(String key, int val) {
        if (map.containsKey(key)) {
            map.remove(key);
        }
        map.put(key, val);
    }

    public int sum(String prefix) {
        int sum = 0;
        for (String s : map.keySet()) {
            if (s.startsWith(prefix)) {
                sum += map.get(s);
            }
        }
        return sum;
    }

看到一个时间是O(len(key))的方法，维护两个map，每次都更新比给定key短的所有key的value。
https://discuss.leetcode.com/topic/103908/simple-java-hashmap-solution-o-1-sum-and-o-len-key-insert

/** Initialize your data structure here. */
Map<String, Integer> map;
Map<String, Integer> original;
public MapSum() {
    map = new HashMap<>();
    original = new HashMap<>();
}

public void insert(String key, int val) {
    val -= original.getOrDefault(key, 0); // calculate the diff to be added to prefixes
    String s = "";
    for(char c : key.toCharArray()) {
        s += c; // creating all prefixes
        map.put(s, map.getOrDefault(s, 0) + val); //update/insert all prefixes with new value
    }
    original.put(key, original.getOrDefault(key, 0) + val);
}

public int sum(String prefix) {
    return map.getOrDefault(prefix, 0);
}