LeetCode 键值映射题解
题目描述
设计一个 map，支持插入键值对和返回以给定前缀开头的所有键对应的值的总和。
示例：
map = new TrieMap(); map.insert("apple", 3); map.sum("ap"); // 返回 5解题思路
方法：字典树
思路：
- 在字典树的每个节点中维护一个值总和。
- 插入时，增加路径上所有节点的值总和。
- 查询时，返回对应节点的值总和。
复杂度分析：
- 时间复杂度：O(L)，L 是字符串长度。
- 空间复杂度：O(L)。
代码实现
class TrieNode: def __init__(self): self.children = {} self.value = 0 self.sum = 0 class TrieMap: def __init__(self): self.root = TrieNode() def insert(self, key, val): node = self.root for char in key: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.sum += val node.value = val def sum(self, prefix): node = self.root for char in prefix: if char not in node.children: return 0 node = node.children[char] return node.sum # 测试 def test_trie_map(): map = TrieMap() map.insert("apple", 3) print(map.sum("ap")) # 输出：3 if __name__ == "__main__": test_trie_map()总结
字典树可以维护前缀值总和，通过在每个节点存储值总和，实现高效的前缀求和查询。
