题目描述：
Implement a MapSum class with insert, and sum methods.
For the method insert, you'll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.
For the method sum, you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix.
Example 1:
Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5
题目大意：
设计一个数据结构MapSum，支持insert和sum操作。
insert(key, val)：向MapSum中插入一个key，对应一个val（当key存在时，替换对应的val）
sum(prefix)：求MapSum中对应前缀为prefix的所有key的val之和
解题思路：
字典树（Trie）
TrieNode包含属性：sum（当前节点子树的和），val（当前节点的值）
insert操作：向字典树中插入节点，并将沿途节点记录下来。更新途经节点的sum值 sum操作：直接返回前缀对应节点的sum值
Python代码：
class TrieNode:
# Initialize your data structure here.
def __init__(self):
self.children = dict()
self.sum = 0
self.val = 0
class MapSum(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def insert(self, key, val):
"""
:type key: str
:type val: int
:rtype: void
"""
node = self.root
nodes = []
for letter in key:
child = node.children.get(letter)
if child is None:
child = TrieNode()
node.children[letter] = child
nodes.append(child)
node = child
if node.val != val:
delta = val - node.val
node.val = val
for node in nodes:
node.sum += delta
def sum(self, prefix):
"""
:type prefix: str
:rtype: int
"""
node = self.root
for letter in prefix:
node = node.children.get(letter)
if node is None: return 0
return node.sum
# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)
本文链接：http://bookshadow.com/weblog/2017/09/17/leetcode-map-sum-pairs/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
