字典算法题分类解析

在算法题中，“字典”通常指两种数据结构：

1. 哈希表（HashMap/HashSet）：用于快速查找、计数、映射关系
2. 字典树（Trie/前缀树）：用于处理字符串前缀相关的问题

一、哈希表基础应用（HashMap/HashSet）

类型特点：哈希表的核心能力是 O(1) 平均时间复杂度的插入、删除和查找。常用于：

• 快速查找：判断元素是否存在、两数之和
• 频率统计：计数、词频分析
• 映射关系：建立键值对映射、双向映射
• 去重：记录已访问元素

难度	题目	核心思路简介
简单	1. 两数之和	用 Map 存储元素值和下标，遍历时查找 target - nums[i]
简单	217. 存在重复元素	用 Set 判断是否有重复元素
简单	242. 有效的字母异位词	统计两字符串字符频率是否相同
简单	349. 两个数组的交集	用 Set 存储一个数组，遍历另一个数组判断是否存在
简单	383. 赎金信	用 Map 统计 magazine 字符出现次数，检查 ransomNote 是否够用
简单	202. 快乐数	用 Set 记录出现过的数，判断是否进入循环
简单	136. 只出现一次的数字	可用 Set（出现两次则删除），但更优解是异或
中等	49. 字母异位词分组	将排序后的字符串作为 Map 的键，分组存储
中等	3. 无重复字符的最长子串	用 Map 存储字符最近出现的位置，滑动窗口时更新左边界
中等	347. 前 K 个高频元素	先用 Map 统计频率，再用优先队列（堆）取 Top K
中等	560. 和为 K 的子数组	前缀和 + Map 优化，Map 存储前缀和出现的次数
中等	205. 同构字符串	建立双向映射关系，两个 Map 分别存储 s->t 和 t->s 的映射
中等	290. 单词规律	类似同构字符串，建立 pattern->word 和 word->pattern 的双向映射
中等	454. 四数相加 II	将前两个数组的和存入 Map 计数，遍历后两个数组查找补数
中等	36. 有效的数独	用三个二维数组或 Set 记录行、列、九宫格中已出现的数字

二、字典树（Trie/前缀树）

类型特点：字典树是一种树型结构，用于处理字符串前缀相关的问题。核心操作是插入和查找，时间复杂度 O(len(key))。适用于：

• 前缀匹配：判断是否存在以某前缀开头的单词
• 模糊搜索：支持通配符匹配
• 单词查找：在字典中查找单词是否存在
• 公共前缀统计：利用字符串公共前缀减少空间消耗

难度	题目	核心思路简介
中等	208. 实现 Trie (前缀树)	实现 Trie 的 insert、search、startsWith 方法
中等	211. 添加与搜索单词 - 数据结构设计	Trie + DFS 处理通配符 '.' 的匹配
困难	212. 单词搜索 II	Trie + 回溯，将单词存入 Trie，在矩阵中 DFS 搜索
中等	648. 单词替换	将词根存入 Trie，遍历句子中的单词查找最短词根替换
中等	677. 键值映射	Trie 节点存储值，insert 时更新路径上的前缀和
中等	720. 词典中最长的单词	将单词存入 Trie，DFS 查找所有前缀都存在的单词
困难	472. 连接词	Trie + DFS + 记忆化，判断单词是否由其他单词组成
中等	820. 单词的压缩编码	将单词反转后存入 Trie，统计叶子节点深度和
困难	1032. 字符流	构建后缀 Trie（反向插入），在字符流中匹配历史查询
中等	1268. 搜索推荐系统	Trie + DFS，每输入一个前缀返回前 3 个推荐单词
中等	1233. 删除子文件夹	将文件夹路径存入 Trie，标记结束节点，DFS 收集完整路径
中等	676. 实现一个魔法字典	Trie + DFS，搜索时允许一次字符不匹配

三、综合应用（哈希表 + 其他数据结构）

类型特点：哈希表与其他数据结构结合，实现更复杂的功能：

• 哈希表 + 双向链表：实现 LRU 缓存
• 哈希表 + 堆：实现 Top K 问题
• 哈希表 + 数组：实现 O(1) 随机访问

难度	题目	核心思路简介
中等	146. LRU 缓存	哈希表 + 双向链表实现 O(1) 的 get 和 put
中等	380. O(1) 时间插入、删除和获取随机元素	哈希表 + 动态数组，哈希表存储值到数组下标的映射
困难	895. 最大频率栈	哈希表记录频率到对应元素栈的映射，以及元素到频率的映射
中等	355. 设计推特	哈希表 + 优先队列（堆）实现推文推送

哈希表解题模板（JavaScript）

1. 计数模板

// 统计频率
const freq = new Map();
for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
}

2. 两数之和模板

const map = new Map();
for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
        return [map.get(complement), i];
    }
    map.set(nums[i], i);
}

3. 前缀和 + 哈希模板

const map = new Map();
map.set(0, 1); // 前缀和为0出现1次
let sum = 0, count = 0;
for (const num of nums) {
    sum += num;
    if (map.has(sum - k)) {
        count += map.get(sum - k);
    }
    map.set(sum, (map.get(sum) || 0) + 1);
}

4. 双向映射模板

const map1 = new Map();
const map2 = new Map();
// 确保双向映射一致
if (map1.get(a) !== b || map2.get(b) !== a) {
    return false;
}

字典树（Trie）JavaScript 模板

var Trie = function() {
    this.children = {};
    this.isEnd = false; // 表示是否是单词结尾
    // 可以添加额外属性，如 count 记录出现次数
};

Trie.prototype.insert = function(word) {
    let node = this;
    for (let char of word) {
        if (!node.children[char]) {
            node.children[char] = new Trie();
        }
        node = node.children[char];
    }
    node.isEnd = true;
};

Trie.prototype.search = function(word) {
    let node = this;
    for (let char of word) {
        if (!node.children[char]) return false;
        node = node.children[char];
    }
    return node.isEnd === true;
};

Trie.prototype.startsWith = function(prefix) {
    let node = this;
    for (let char of prefix) {
        if (!node.children[char]) return false;
        node = node.children[char];
    }
    return true;
};

复杂度分析：

• 插入和查询时间复杂度：O(len(key))
• 建树最坏空间复杂度：O(mⁿ)，m 是字符集大小，n 是字符串长度

刷题建议

1. 哈希表基础：从 1. 两数之和、217. 存在重复元素、242. 有效的字母异位词 入手
2. 哈希表进阶：练习 49. 字母异位词分组、560. 和为 K 的子数组
3. 字典树入门：从 208. 实现 Trie (前缀树) 开始，理解 Trie 的基本操作
4. 字典树进阶：挑战 211. 添加与搜索单词、212. 单词搜索 II
5. 综合应用：最后尝试 146. LRU 缓存、380. O(1) 时间插入