原文链接: https://leetcode-cn.com/problems/map-sum-pairs

英文原文

Design a map that allows you to do the following:

• Maps a string key to a given value.
• Returns the sum of the values that have a key with a prefix equal to a given string.

Implement the MapSum class:

• MapSum() Initializes the MapSum object.
• void insert(String key, int val) Inserts the key-val pair into the map. If the key already existed, the original key-value pair will be overridden to the new one.
• int sum(string prefix) Returns the sum of all the pairs' value whose key starts with the prefix.

 

Example 1:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

 

Constraints:

• 1 <= key.length, prefix.length <= 50
• key and prefix consist of only lowercase English letters.
• 1 <= val <= 1000
• At most 50 calls will be made to insert and sum.

中文题目

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

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

 

示例：

输入：
["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");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

 

提示：

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

通过代码

高赞题解

Trie + DFS

从需要实现「存储字符串（映射关系）」并「检索某个字符串前缀的总和」来看，可以知道这是与 $Trie$ 相关的题目，还不了解 $Trie$ 的同学可以先看前置 🧀：实现 Trie (前缀树) 。

考虑如何实现两个操作：

• insert ：在基本的 $Trie$ 插入操作的基础上进行拓展即可。与常规的插入操作的唯一区别为，不能简单记录单词的结束位置，还要存储 $key$ 对应的 $val$ 是多少。具体的我们可以使用 int 类型的数组 $hash$ 来代替原有的 boolean 类型的数组 $isWord$；

• sum ： 先对入参 $prefix$ 进行字典树搜索，到达尾部后再使用 DFS 搜索后面的所有方案，并累加结果。

代码（static 优化代码见 $P2$，避免每个样例都 new 大数组）：

[]
class MapSum {
    int[][] tr = new int[2510][26];
    int[] hash = new int[2510];
    int idx;
    public void insert(String key, int val) {
        int p = 0;
        for (int i = 0; i < key.length(); i++) {
            int u = key.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
        }
        hash[p] = val;
    }
    public int sum(String prefix) {
        int p = 0;
        for (int i = 0; i < prefix.length(); i++) {
            int u = prefix.charAt(i) - 'a';
            if (tr[p][u] == 0) return 0;
            p = tr[p][u];
        }
        return dfs(p);
    }
    int dfs(int p) {
        int ans = hash[p];
        for (int u = 0; u < 26; u++) {
            if (tr[p][u] != 0) ans += dfs(tr[p][u]);
        }
        return ans;
    }
}

[]
class MapSum {
    static int[][] tr = new int[2510][26];
    static int[] hash = new int[2510];
    static int idx;
    public MapSum() {
        for (int i = 0; i <= idx; i++) Arrays.fill(tr[i], 0);
        Arrays.fill(hash, 0);
        idx = 0;
    }
    public void insert(String key, int val) {
        int p = 0;
        for (int i = 0; i < key.length(); i++) {
            int u = key.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
        }
        hash[p] = val;
    }
    public int sum(String prefix) {
        int p = 0;
        for (int i = 0; i < prefix.length(); i++) {
            int u = prefix.charAt(i) - 'a';
            if (tr[p][u] == 0) return 0;
            p = tr[p][u];
        }
        return dfs(p);
    }
    int dfs(int p) {
        int ans = hash[p];
        for (int u = 0; u < 26; u++) {
            if (tr[p][u] != 0) ans += dfs(tr[p][u]);
        }
        return ans;
    }
}

• 时间复杂度：令 $key$ 的最大长度为 $n$，最大调用次数为 $m$，字符集大小为 $C$（ 本题 $C$ 固定为 $26$ ），insert 操作的复杂度为 $O(n)$；从 DFS 的角度分析，sum 操作的复杂度为 $O(C^n)$，但事实上，对于本题具有明确的计算量上界，搜索所有的格子的复杂度为 $O(n * m * C)$
• 空间复杂度：$O(n * m * C)$

---

Trie 记录前缀字符串总和

为降低 sum 操作的复杂度，我们可以在 insert 操作中同时记录（累加）每个前缀的总和。

代码（static 优化代码见 $P2$，避免每个样例都 new 大数组）：

[]
class MapSum {
    int N = 2510;
    int[][] tr = new int[N][26];
    int[] hash = new int[N];
    int idx;
    Map<String, Integer> map = new HashMap<>();
    public void insert(String key, int val) {
        int _val = val;
        if (map.containsKey(key)) val -= map.get(key);
        map.put(key, _val);
        for (int i = 0, p = 0; i < key.length(); i++) {
            int u = key.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
            hash[p] += val;
        }
    }
    public int sum(String prefix) {
        int p = 0;
        for (int i = 0; i < prefix.length(); i++) {
            int u = prefix.charAt(i) - 'a';
            if (tr[p][u] == 0) return 0;
            p = tr[p][u];
        }
        return hash[p];
    }
}

[]
class MapSum {
    static int N = 2510;
    static int[][] tr = new int[N][26];
    static int[] hash = new int[N];
    static int idx;
    static Map<String, Integer> map = new HashMap<>();
    public MapSum() {
        for (int i = 0; i <= idx; i++) Arrays.fill(tr[i], 0);
        Arrays.fill(hash, 0);
        idx = 0;
        map.clear();
    }
    public void insert(String key, int val) {
        int _val = val;
        if (map.containsKey(key)) val -= map.get(key);
        map.put(key, _val);
        for (int i = 0, p = 0; i < key.length(); i++) {
            int u = key.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
            hash[p] += val;
        }
    }
    public int sum(String prefix) {
        int p = 0;
        for (int i = 0; i < prefix.length(); i++) {
            int u = prefix.charAt(i) - 'a';
            if (tr[p][u] == 0) return 0;
            p = tr[p][u];
        }
        return hash[p];
    }
}

• 时间复杂度：令 $key$ 的最大长度为 $n$，insert 操作的复杂度为 $O(n)$；sum 操作的复杂度为 $O(n)$
• 空间复杂度：令 $key$ 的最大长度为 $n$，最大调用次数为 $m$，字符集大小为 $C$（ 本题 $C$ 固定为 $26$ ），复杂度为 $O(n * m * C)$

---

更多「Trie」相关内容

意犹未尽？考虑加餐如下 $Trie$ 内容：

• $Trie$ 第一部（Trie 模板题）
• $Trie$ 第二部（Trie 优化 DFS 搜索）
• $Trie$ 第三部（结合贪心的 Trie）
• $Trie$ 第四部（可删除/可计数的 Trie）

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
36879	55308	66.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言