forked from heqin-zhu/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmapSum.py
More file actions
80 lines (72 loc) · 2.23 KB
/
mapSum.py
File metadata and controls
80 lines (72 loc) · 2.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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#coding: utf-8
''' mbinary
#######################################################################
# File : mapSum.py
# Author: mbinary
# Mail: [email protected]
# Blog: https://mbinary.xyz
# Github: https://github.com/mbinary
# Created Time: 2018-12-14 23:11
# Description:
实现一个 MapSum 类里的两个方法，insert 和 sum。
对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。
对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。
示例 1:
输入: insert("apple", 3), 输出: Null
输入: sum("ap"), 输出: 3
输入: insert("app", 2), 输出: Null
输入: sum("ap"), 输出: 5
leetcode-ch:677 https://leetcode-cn.com/problems/map-sum-pairs/
#######################################################################
'''
class node:
def __init__(self,ch,n=0):
self.ch = ch
self.n = n
self.children={}
def __getitem__(self,ch):
return self.children[ch]
def __setitem__(self,ch,nd):
self.children[ch]=nd
def __len__(self):
return len(self.children)
def __iter__(self):
return iter(self.children.values())
def __delitem(self,ch):
del self.children[ch]
def __contains__(self,ch):
return ch in self.children
class MapSum:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = node('')
def insert(self, key, val):
"""
:type key: str
:type val: int
:rtype: void
"""
nd = self.root
for i in key:
if i not in nd:
nd[i] = node(i)
nd = nd[i]
nd.n = val
def visit(self,nd):
ret = nd.n
for chd in nd:
ret+=self.visit(chd)
return ret
def sum(self, prefix):
"""
:type prefix: str
:rtype: int
"""
nd = self.root
for ch in prefix:
if ch in nd:
nd = nd[ch]
else:return 0
return self.visit(nd)