677. Map Sum Pairs

Approach 1: Hash Map Counting

We can simply keep a track of the words and their counts. Once we're asked to check a prefix we can simply iterate over the keys and add up the counts one by one

class MapSum(object):
# https://leetcode.com/problems/map-sum-pairs/description/
def __init__(self):
"""
Initialize your data structure here.
"""
self.di = {}
def insert(self, key, val):
"""
:type key: str
:type val: int
:rtype: void
"""
self.di[key] = val
def sum(self, prefix):
"""
:type prefix: str
:rtype: int
"""
count = 0
for i in self.di:
if i.startswith(prefix):
count += self.di[i]
return count
# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)

Time Complexity: O(K^2), where K is the average length of the string

Space Complexity: O(N), where N is the number of words