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()
   = {}
        def insert(self, key, val):
            delta = val -, 0)
  [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.