Python, Trie Solution (different from article)


  • 1

    Here is my alternate Trie solution. For the more standard version, please check the article for this problem.

    Trie = lambda: collections.defaultdict(Trie)
    SUM = False
    
    class MapSum(object):
        def __init__(self):
            self.trie = Trie()
            self.map = {}
    
        def insert(self, key, val):
            delta = val - self.map.get(key, 0)
            self.map[key] = val
            cur = self.trie
            for char in key:
                cur = cur[char]
                cur[SUM] = cur.get(SUM, 0) + delta
    
        def sum(self, prefix):
            cur = self.trie
            for char in prefix:
                if char not in cur: return 0
                cur = cur[char]
            return cur[SUM]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.