难度: Medium
原题连接
内容描述
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
思路 1 - 时间复杂度: O(1) insert + O(N * P) sum- 空间复杂度: O(N)******
时间复杂度中的 N 是the number of items in the map，P 是 the length of the input prefix. 暴力解法, beats 39.30%
class MapSum:
def __init__(self):
"""
Initialize your data structure here.
"""
self.lookup = {}
def insert(self, key, val):
"""
:type key: str
:type val: int
:rtype: void
"""
self.lookup[key] = val
def sum(self, prefix):
"""
:type prefix: str
:rtype: int
"""
return sum(v for k, v in self.lookup.items() if k.startswith(prefix))思路 2 - 时间复杂度: O(K^2) insert + O(1) sum- 空间复杂度: O(N)******
时间复杂度中的 K 是 the length of the input key.
暴力解法, beats 42.20%
class MapSum:
def __init__(self):
"""
Initialize your data structure here.
"""
self.lookup = collections.defaultdict(int)
self.pref_lookup = collections.defaultdict(int)
def insert(self, key, val):
"""
:type key: str
:type val: int
:rtype: void
"""
diff = val - self.lookup[key]
self.lookup[key] = val
for i in range(len(key)+1):
prefix = key[:i]
self.pref_lookup[prefix] += diff
def sum(self, prefix):
"""
:type prefix: str
:rtype: int
"""
return self.pref_lookup[prefix]思路 3 - 时间复杂度: O(K) insert + O(1) sum- 空间复杂度: O(N)******
时间复杂度中的 K 是 the length of the input key.
Trie 树, beats 30.50%
class TrieNode(object):
def __init__(self):
self.children = dict()
self.isWordEnd = False
self.score = 0
def buildTrie(self, words):
for word in words:
curr = self
for char in word:
if char not in curr.children:
curr.children[char] = TrieNode()
curr = curr.children[char]
curr.isWordEnd = True
def find(self, word):
curr = self
for char in word:
if char not in curr.children:
return False
curr = curr.children[char]
return curr.isWordEnd
class MapSum:
def __init__(self):
"""
Initialize your data structure here.
"""
self.lookup = collections.defaultdict(int)
self.root = TrieNode()
def insert(self, key, val):
"""
:type key: str
:type val: int
:rtype: void
"""
diff = val - self.lookup[key]
self.lookup[key] = val
cur = self.root
cur.buildTrie([key])
for c in key:
cur = cur.children[c]
cur.score += diff
def sum(self, prefix):
"""
:type prefix: str
:rtype: int
"""
cur = self.root
for c in prefix:
if c not in cur.children:
return 0
cur = cur.children[c]
return cur.score可以写的更简便一些
class TrieNode(object):
def __init__(self):
self.children = dict()
self.score = 0
class MapSum:
def __init__(self):
"""
Initialize your data structure here.
"""
self.lookup = collections.defaultdict(int)
self.root = TrieNode()
def insert(self, key, val):
"""
:type key: str
:type val: int
:rtype: void
"""
diff = val - self.lookup[key]
self.lookup[key] = val
cur = self.root
for c in key:
cur = cur.children.setdefault(c, TrieNode())
cur.score += diff
def sum(self, prefix):
"""
:type prefix: str
:rtype: int
"""
cur = self.root
for c in prefix:
if c not in cur.children:
return 0
cur = cur.children[c]
return cur.score