题目
难度：★★★☆☆
类型：字符串
方法：前缀树
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
实现一个 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解决方案，请移步力扣中等题解析
