LeetCode 键值映射题解

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()

总结

字典树可以维护前缀值总和，通过在每个节点存储值总和，实现高效的前缀求和查询。