题目

难度：★★★☆☆
类型：字符串
方法：前缀树

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

实现一个 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

解答

方法1：直接计算

用直来直去的逻辑，加上python方便快捷的风格，可以快速实现：

class MapSum:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dct = dict()

    def insert(self, key: str, val: int) -> None:
        self.dct.update({key: val})

    def sum(self, prefix: str) -> int:
        return sum([v for k, v in self.dct.items() if k.startswith(prefix)])

方法2：前缀树

要是只会用上面的方法可能失去了这道题的意义，这里推荐一种更快捷的前缀树方法。将所有单词根据共同前缀构建一前缀树，每个叶子节点上都有一个特定数值的果实，拥有相同前缀的集合实际上挂在一棵树杈上，用深度优先搜索的方法将这棵子树上所有的果实采摘即可。

这里详细写出了构建这棵树以及用深度优先搜索进行采摘的流程。

class MapSum:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dct = dict()

    def insert(self, key: str, val: int) -> None:
        tmp = self.dct
        for c in key:
            if c not in tmp:
                tmp[c] = dict()
            tmp = tmp[c]
        tmp.update({'val': val})

    def sum(self, prefix: str) -> int:
        tmp = self.dct
        for c in prefix:
            if c in tmp:
                tmp = tmp[c]
            else:
                return 0

        def get_sum_of_subtree(node):
            for k, v in node.items():
                if k == 'val':
                    nonlocal s
                    s = s + v
                else:
                    get_sum_of_subtree(v)

        s = 0
        get_sum_of_subtree(tmp)
        return s

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析