LeetCode 677. 键值映射

约 6 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
字符串 哈希表 设计 字典树

题目描述

✅ 677. 键值映射

image-20260929104522562

image-20260929104523023

题意分析

支持插入字符串键及其整数值，同一个键再次插入时用新值覆盖旧值；查询一个前缀时，返回所有以它开头的键的当前值之和。

多个键可能共享前缀。可以用字典树共享这些路径，并在每个前缀节点保存累计和，使查询不必再扫描全部键。

解法：Trie + 增量更新

核心思路

[!blue]

字典树中，从根走到某节点的字符路径代表一个前缀，节点的 sum 保存所有以该前缀开头的键值总和，包括键恰好等于此前缀的情况。插入一个键时，它对总和有贡献的前缀，正好就是键路径上的各个节点。

另用哈希映射保存每个完整键当前的值。插入前先取出旧值 old，不存在时按 0 处理，计算 delta = val-old，再更新映射。沿键的字典树路径，把 delta 加到每个经过的节点；缺失的节点先创建。

这样更新是正确的，因为此次只有一个键的贡献发生变化：包含该键的前缀总和都应该增加 val-old，其他前缀总和应该保持不变。更新范围恰好对应它的路径，因此所有节点的累计和都能继续保持正确。新键相当于从零增加到新值，覆盖为更小值时差值为负，同值覆盖时差值为零。

查询时只需按前缀逐字符走下去。如果路径中途不存在，说明没有任何键具有这个前缀，返回 0；如果成功到达，就直接返回该节点的 sum。前缀本身不必是一个已经插入的完整键，因此无需检查单词结束标记。代码也同步维护根节点的总和，表示所有键的总贡献。

解题步骤

  1. 初始化字典树根节点和保存完整键当前值的映射。
  2. 插入时先读取旧值、算出差值，再把映射中的值更新为新值。
  3. 从根沿键逐字符下降，按需创建节点，把差值累加到根和每个路径节点。
  4. 查询时沿前缀路径下降，路径缺失返回 0，否则返回终点节点保存的总和。

代码实现

class MapSum {
    private static class Node {
        Node[] next = new Node[26];
        int sum;
    }

    private final Node root = new Node();
    private final Map<String, Integer> map = new HashMap<>();

    public void insert(String key, int val) {
        int old = map.getOrDefault(key, 0);
        // 覆盖插入只传播新旧差值，避免把旧贡献再次累加。
        int delta = val - old;

        map.put(key, val);

        Node cur = root;

        cur.sum += delta;

        for (int i = 0; i < key.length(); i++) {
            int idx = key.charAt(i) - 'a';

            if (cur.next[idx] == null) {
                cur.next[idx] = new Node();
            }

            cur = cur.next[idx];
            cur.sum += delta;
        }
    }

    public int sum(String prefix) {
        Node cur = root;

        for (int i = 0; i < prefix.length(); i++) {
            int idx = prefix.charAt(i) - 'a';

            if (cur.next[idx] == null) {
                return 0;
            }

            cur = cur.next[idx];
        }

        return cur.sum;
    }
}

type trieNode677 struct {
    next [26]*trieNode677
    sum  int
}

type MapSum struct {
    root *trieNode677
    mp   map[string]int
}

func Constructor() MapSum {
    return MapSum{
        root: &trieNode677{},
        mp:   make(map[string]int),
    }
}

func (m *MapSum) Insert(key string, val int) {
    old := m.mp[key]
    // 覆盖插入只传播新旧差值，避免把旧贡献再次累加。
    delta := val - old
    m.mp[key] = val

    cur := m.root
    cur.sum += delta
    for i := 0; i < len(key); i++ {
        idx := int(key[i] - 'a')
        if cur.next[idx] == nil {
            cur.next[idx] = &trieNode677{}
        }
        cur = cur.next[idx]
        cur.sum += delta
    }
}

func (m *MapSum) Sum(prefix string) int {
    cur := m.root
    for i := 0; i < len(prefix); i++ {
        idx := int(prefix[i] - 'a')
        if cur.next[idx] == nil {
            return 0
        }
        cur = cur.next[idx]
    }
    return cur.sum
}

复杂度分析

  • 时间复杂度：插入期望 $O(L)$，L 为键长，哈希键值查询和字典树更新都在线性范围内；前缀查询为 $O(P)$，P 为前缀长度。
  • 空间复杂度：$O(D)$，D 为所有不同键的总长度。字典树节点数不超过此前缀总量上界，键值映射也只保留每个不同键的一份当前记录。

关键点总结

[!green]

  • 节点累计和按前缀聚合，既包含该前缀本身对应的键，也包含更长的后代键。
  • 覆盖操作先扣除旧贡献再加入新贡献，两步合成差值即可一次传播。
  • 完整键值映射负责区分新增与覆盖，字典树负责共享前缀和快速查询。
  • 查询前缀不要求它本身是完整键，只要求对应路径存在。

易错点总结

[!yellow]

  • 每次插入都直接累加新值，会在覆盖时重复保留旧贡献。
  • 先覆盖映射再读取旧值，会让差值错误地变为零；应提前保存旧值。
  • 只更新键的末尾节点，会让中间前缀的累计和保持旧值。
  • 拒绝负差值，会使降低已有键值的覆盖操作失效。
  • 只统计严格更长的后代键，会遗漏恰好与查询前缀相同的键。

相似题目

题目 难度 关联与区别
208. 实现 Trie (前缀树) 中等 前缀路径结构相同，本题节点还聚合所有后代单词的值。
211. 添加与搜索单词 - 数据结构设计 中等 用字典树共享字符串前缀；本题在前缀节点累计键值总和，该题通配符查询时分支搜索。
212. 单词搜索 II 困难 用字典树共享字符串前缀；本题在前缀节点累计键值总和，该题把字典树与网格回溯结合。
648. 单词替换 中等 用字典树共享字符串前缀；本题在前缀节点累计键值总和，该题沿词前缀找到最短词根。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/27459352
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！