描述

实现一个 MapSum 类，支持两个方法，insert 和 sum：

  • MapSum() 初始化 MapSum 对象
  • void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
  • int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。

示例

  1. 输入：
  2. inputs = ["MapSum", "insert", "sum", "insert", "sum"]
  3. inputs = [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
  4. 输出：
  5. [null, null, 3, null, 5]
  7. 解释：
  8. MapSum mapSum = new MapSum();
  9. mapSum.insert("apple", 3);  
  10. mapSum.sum("ap");           // return 3 (apple = 3)
  11. mapSum.insert("app", 2);    
  12. mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

提示

  • 1 <= key.length, prefix.length <= 50
  • key 和 prefix 仅由小写英文字母组成
  • 1 <= val <= 1000
  • 最多调用 50 次 insert 和 sum

解题思路

前缀树

在经典前缀树算法下做以下改动：

  1. 用 val 记录每个节点的值，对于 insert 操作，每有一个 char 走到当前节点，节点的 val 会加上这个字符串的值。
  2. 用一个 hashMap 保存插入的键值对，如果是重复的键，要减去原来的值。
  3. 对于 sum 操作，如果 node.children[ch - 'a'] == null，则说明这个字符串不是任何前缀树中的前缀，直接返回0；否则，更新 node 为 node = node.children[ch - 'a']，最后更新 res 为 node.val,返回res;
  • 解法最重要的逻辑是：节点的值记录的是前缀树中所有经过这个节点的值的总和，在前缀树中遍历字符串prefix时，最后一个字符的节点的值就是所有以该前缀 prefix 开头的键 key 的值的总和

代码

class MapSum {
    MapSum[] children;
    int val;
    Map<String, Integer> map;
    /** Initialize your data structure here. */
    public MapSum() {
        children = new MapSum[26];
        val = 0;
        map = new HashMap<>();
    }

    public void insert(String key, int val) {
        MapSum node = this;
        for (int i = 0; i < key.length(); i++) {
            int index = key.charAt(i) - 'a';
            if (node.children[index] == null) {
                node.children[index] = new MapSum();
            }
            if (map.containsKey(key)) {
                node.children[index].val -= map.get(key);
            }
            node.children[index].val += val;
            node = node.children[index];
        }
        map.put(key, val);
    }

    public int sum(String prefix) {
        MapSum node = this;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if (node.children[index] == null) {
                return 0;
            }
            node = node.children[index];
        }
        return node.val;
    }
}