键值映射

🎯 问题描述（来源于LeetCode）

描述：
设计一个 map ，满足以下几点:

  • 字符串表示键，整数表示值

  • 返回具有前缀等于给定字符串的键的值的总和
    实现一个 MapSum 类：

  • MapSum() 初始化 MapSum 对象

  • void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对 key-value 将被替代成新的键值对。

  • int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
    说明：

  • 1 <= key.length, prefix.length <= 50

  • key 和 prefix 仅由小写英文字母组成

  • 1 <= val <= 1000

  • 最多调用 50 次 insert 和 sum
    示例：

  • 示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：
["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：字典树

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class TrieNode:
    def __init__(self):
        self.children = {}
        self.val = 0          # 存储单词的值，仅单词结尾节点非零

class MapSum:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, key: str, val: int) -> None:
        node = self.root
        for ch in key:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.val = val          # 正确存储到节点

    def sum(self, prefix: str) -> int:
        node = self.root
        # 定位到前缀的最后一个节点
        for ch in prefix:
            if ch not in node.children:
                return 0
            node = node.children[ch]
        # DFS 累加所有单词的值
        total = 0
        stack = [node]
        while stack:
            cur = stack.pop()
            total += cur.val
            for child in cur.children.values():
                stack.append(child)
        return total

思路1：📊 性能分析

提交结果
  • 运行时间：3ms击败29.17%
  • 内存消耗：19.16MB击败79.17%