python solution using Trie and DFS

  • 0
    class MapSum(object):
        def __init__(self):
            self.root = {}
        def insert(self, key, val):
            node = self.root
            for ch in key:
                node = node.setdefault(ch, {})
            node['val'] = val
        def sum(self, prefix):
            def dfs(parent):
                return sum([child if isinstance(child, int) else dfs(child) for child in parent.values()])
            node = self.root
            for ch in prefix:
                if ch not in node:
                    return 0
                node = node[ch]
            return dfs(node)

Log in to reply

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