LeetCode 题解工作台
键值映射
设计一个 map ，满足以下几点: 字符串表示键，整数表示值 返回具有前缀等于给定字符串的键的值的总和 实现一个 MapSum 类： MapSum() 初始化 MapSum 对象 void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，…
4
题型
8
代码语言
3
相关题
当前训练重点
中等 · 哈希·表·结合·string
答案摘要
我们用哈希表 存放键值对，用前缀树 存放键值对的前缀和。前缀树的每个节点包含两个信息： - `val`：以该节点为前缀的键值对的值的总和
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·表·结合·string 题型思路
题目描述
设计一个 map ，满足以下几点:
- 字符串表示键，整数表示值
- 返回具有前缀等于给定字符串的键的值的总和
实现一个 MapSum 类：
MapSum()初始化MapSum对象void insert(String key, int val)插入key-val键值对，字符串表示键key，整数表示值val。如果键key已经存在，那么原来的键值对key-value将被替代成新的键值对。int sum(string prefix)返回所有以该前缀prefix开头的键key的值的总和。
示例 1：
输入：
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
输出：
[null, null, 3, null, 5]
解释：
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap"); // 返回 3 (apple = 3)
mapSum.insert("app", 2);
mapSum.sum("ap"); // 返回 5 (apple + app = 3 + 2 = 5)
提示：
1 <= key.length, prefix.length <= 50key和prefix仅由小写英文字母组成1 <= val <= 1000- 最多调用
50次insert和sum
解题思路
方法一：哈希表 + 前缀树
我们用哈希表 存放键值对，用前缀树 存放键值对的前缀和。前缀树的每个节点包含两个信息：
val：以该节点为前缀的键值对的值的总和children：长度为 的数组，存放该节点的子节点
插入键值对 时，我们先判断哈希表是否存在该键，如果存在，那么前缀树每个节点的 val 都要减去该键原来的值，然后再加上新的值。如果不存在，那么前缀树每个节点的 val 都要加上新的值。
查询前缀和时，我们从前缀树的根节点开始，遍历前缀字符串，如果当前节点的子节点中不存在该字符，那么说明前缀树中不存在该前缀，返回 。否则，继续遍历下一个字符，直到遍历完前缀字符串，返回当前节点的 val。
时间复杂度方面，插入键值对的时间复杂度为 ，其中 为键的长度。查询前缀和的时间复杂度为 ，其中 为前缀的长度。
空间复杂度 ，其中 和 分别是键的数量以及键的最大长度；而 是字符集的大小，本题中 。
class Trie:
def __init__(self):
self.children: List[Trie | None] = [None] * 26
self.val: int = 0
def insert(self, w: str, x: int):
node = self
for c in w:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.val += x
def search(self, w: str) -> int:
node = self
for c in w:
idx = ord(c) - ord('a')
if node.children[idx] is None:
return 0
node = node.children[idx]
return node.val
class MapSum:
def __init__(self):
self.d = defaultdict(int)
self.tree = Trie()
def insert(self, key: str, val: int) -> None:
x = val - self.d[key]
self.d[key] = val
self.tree.insert(key, x)
def sum(self, prefix: str) -> int:
return self.tree.search(prefix)
# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Every insert operation is |
| 空间 | The space used is linear in the size of the total input |
面试官常问的追问
外企场景- question_mark
Can the candidate design efficient insert and sum methods?
- question_mark
Does the candidate understand the trade-offs between hash tables and trie structures for prefix-based queries?
- question_mark
How well does the candidate handle updates to the data structure and ensure consistent results in subsequent queries?
常见陷阱
外企场景- error
Not considering how to handle key updates efficiently, potentially leading to incorrect sum results.
- error
Inefficient prefix sum calculation that doesn't leverage a trie structure, resulting in suboptimal performance.
- error
Mismanagement of space, such as storing redundant data in the trie, leading to higher than necessary memory usage.
进阶变体
外企场景- arrow_right_alt
Extend the MapSum class to support deletion of key-value pairs.
- arrow_right_alt
Implement a version of MapSum that supports case-sensitive strings.
- arrow_right_alt
Optimize the solution to handle more than 50 operations efficiently, focusing on scaling.