LeetCode_前缀树_数据结构设计_中等_677.键值映射

1.题目

设计一个 map ，满足以下几点：
① 字符串表示键，整数表示值
② 返回具有前缀等于给定字符串的键的值的总和

实现一个 MapSum 类：

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

示例 1：
输入：
[“MapSum”, “insert”, “sum”, “insert”, “sum”]
[[], [“apple”, 3], [“ap”], [“app”, 2], [“ap”]]
输出：
[null, null, 3, null, 5]

解释：
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // 返回 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // 返回 5 (apple + app = 3 + 2 = 5)

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/map-sum-pairs

2.思路

（1）哈希表
本题可以使用直接哈希表来实现题目的要求，即要将插入的键值对存放到 hashMap 中，而如果要求出以前缀 prefix 开头的键 key 的值的总和，直接遍历 hashMap 中的键值对，判断每个键是否包含前缀 prefix，并用变量 sum 进行累加求和即可。

（2）前缀哈希映射
思路参考本题官方题解。

（3）前缀树
思路参考本题官方题解。

3.代码实现（Java）

//思路1————哈希表
class MapSum {

    Map<String, Integer> hashMap;

    public MapSum() {
        hashMap = new HashMap<>();
    }
    
    public void insert(String key, int val) {
        hashMap.put(key, val);
    }
    
    public int sum(String prefix) {
        int sum = 0;
        for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            if (entry.getKey().startsWith(prefix)) {
                sum += entry.getValue();
            }
        }
        return sum;
    }
}

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

//思路2————前缀哈希映射
class MapSum {

    Map<String, Integer> hashMap;
    Map<String, Integer> prefixMap;

    public MapSum() {
        hashMap = new HashMap<>();
        prefixMap = new HashMap<>();
    }
    
    public void insert(String key, int val) {
        int diff = val - hashMap.getOrDefault(key, 0);
        hashMap.put(key, val);
        for (int i = 1; i <= key.length(); i++) {
            String curPrefix = key.substring(0, i);
            prefixMap.put(curPrefix, prefixMap.getOrDefault(curPrefix, 0) + diff);
        }
    }
    
    public int sum(String prefix) {
        return prefixMap.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);
 */

//思路3————前缀树
class MapSum {

    class TrieNode {
        int val = 0;
        TrieNode[] next = new TrieNode[26];
    }

    Map<String, Integer> hashMap;
    TrieNode root;

    public MapSum() {
        hashMap = new HashMap<>();
        root = new TrieNode();
    }
    
    public void insert(String key, int val) {
        int diff = val - hashMap.getOrDefault(key, 0);
        hashMap.put(key, val);
        TrieNode node = root;
        for (char c : key.toCharArray()) {
            if (node.next[c - 'a'] == null) {
                node.next[c - 'a'] = new TrieNode();
            }
            node = node.next[c - 'a'];
            node.val += diff;
        }
    }
    
    public int sum(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (node.next[c - 'a'] == null) {
                return 0;
            } else {
                node = node.next[c - 'a'];
            }
        }
        return 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);
 */