## 题目描述：

LeetCode 677. Map Sum Pairs

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
```

## 题目大意：

insert(key, val)：向MapSum中插入一个key，对应一个val（当key存在时，替换对应的val）

sum(prefix)：求MapSum中对应前缀为prefix的所有key的val之和

## 解题思路：

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):
"""
"""
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)
``````

Pingbacks已关闭。