Problem statement

https://leetcode.com/problems/map-sum-pairs/

Solution

When you see word prefix in problem formulation, you should definitely think about trie. What we need here is classical trie with one additional field: freq - frequency of each node. For example when we add word apple with val = 3 we need to add this 3 to all a, p, p, l, e nodes. Also we need to deal with this phrase: ` If the key already existed, the original key-value pair will be overridden to the new one, so we need to keep dictionary of pairs key - value to underastand if they already exist in our tree. Then we evaluate delta = val - self.dic.get(key, 0) is amount we need to change our values. For sum function we find node in our tree and if it is not there, return 0`, if we can reach it, return frequency of this node.

Complexity

Time complexity is O(m) to insert key of length m as well it is O(m) to evaluate sum for prefix of length m. Space complexity is O(T) where T it total length of all words.

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.freq = 0

class MapSum:
    def __init__(self):
        self.root = TrieNode()
        self.dic = {}
        
    def insert(self, key, val):
        delta = val - self.dic.get(key, 0)
        self.dic[key] = val
        node = self.root
        node.freq += delta
        for symbol in key:
            node = node.children.setdefault(symbol, TrieNode())
            node.freq += delta
        
    def sum(self, prefix):
        node = self.root
        for symbol in prefix:
            if symbol not in node.children:
                return 0
            node = node.children[symbol]
        return node.freq

Remark

Note, that there is bruteforce solution, where you generate all prefixes and put them into hash table with complexity O(K^2) for each insertion, but which works even faster than trie solution: the reason is that operation with strings: espacially comparison is VERY fast in python, it has speed similar with C/C++ languages: you can try to generate say string aaa.... aaab of length 1000 and compare all substrings of length 500. You will be suprised with resut.