-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path677.py
More file actions
54 lines (43 loc) · 1.23 KB
/
677.py
File metadata and controls
54 lines (43 loc) · 1.23 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Node(object):
def __init__(self, c=''):
self.sum = 0
self.c = c
self.end = False
self.value = 0
self.children = {}
class Trie(object):
def __init__(self):
self.root = Node()
def add(self, key, value):
node = self.root
stack = [node]
for i, k in enumerate(key):
if k not in node.children:
node.children[k] = Node(k)
node = node.children[k]
stack.append(node)
if node.end:
delta = value - node.value
else:
delta = value
node.end = True
for n in stack:
n.sum += delta
def get_sum(self, prefix):
node = self.root
for i, k in enumerate(prefix):
if k not in node.children:
return 0
node = node.children[k]
return node.sum
class MapSum:
def __init__(self):
self.trie = Trie()
def insert(self, key: str, val: int) -> None:
self.trie.add(key, val)
def sum(self, prefix: str) -> int:
return self.trie.get_sum(prefix)
# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)