📚 字典树详解：从字符串前缀搜索到 LeetCode 高频面试题
英文标题 / English Title: Trie Data Structure: From Prefix Search to LeetCode Classics
来源 / Source: LeetCode Blog & 程序员吴师兄
📌 文章简介 / Introduction
字典树（也叫前缀树、Trie）是处理字符串相关问题的利器。它在面试中出现频率很高，尤其是配合回溯、DFS等技巧解决复杂问题时。本文中，我们将从零开始实现 Trie，并结合 LeetCode 高频面试题讲解实际应用。
The Trie (prefix tree) is a powerful data structure for string-related problems. It frequently appears in technical interviews, especially when combined with backtracking or DFS. This article starts from scratch, implements Trie, and solves LeetCode classics.
👉 阅读原文: 字典树详解
🔍 内容要点 / Key Points
1. Trie 的核心思想
字典树的本质是用空间换时间。每个节点存储：
- 子节点映射（字符 → 节点）
- 是否为完整单词的标记
- （可选）以此前缀开头的单词数量
插入和查询都是 O(m)，其中 m 为字符串长度，与数据规模无关。
2. 两种实现方式的对比
| 实现 | 优点 | 缺点 |
|---|---|---|
| 数组（26/128固定） | O(1) 访问，快速 | 空间浪费，字符集大时不适用 |
| 哈希表（字典） | 空间优化，动态 | 访问略慢（哈希计算） |
实际工程中推荐用哈希表，面试时可根据场景选择。
3. Trie 与其他数据结构的配合
- Trie + 回溯：解决单词搜索 II（从每个格子出发 DFS）
- Trie + 排序：按字典序输出所有字符串
- Trie + 贪心：求最长公共前缀
- 压缩Trie：合并单链节点，节省空间（可伸缩Trie）
4. LeetCode 高频题型分类
| 题型 | 代表题 | 难度 |
|---|---|---|
| 基础实现 | 208. 实现 Trie | 中等 |
| 前缀统计 | 820. 单词压缩编码 | 中等 |
| 搜索结合 | 212. 单词搜索 II | 困难 |
| 异位词 | 1804. Trie 前缀对 | 中等 |
💡 学习建议 / Learning Tips
- 先实现基础版：不要一开始就做优化，先把 insert/search/startsWith 三个方法写对。
- 理解词尾标记：很多初学者会在删除或计数时忘记更新这个词尾标记。
- 配合 DFS 一起学：单词搜索 II 是 Trie + DFS 的经典组合，必须掌握。
- 注意内存释放：删除单词时，如果节点变成孤立节点，可以选择释放它（可选优化）。
- 面试加分项：如果面试官追问，可以提到”压缩前缀树（Radix Tree）”的概念，展现实践视野。
| *本文由 AI 自动生成 | Generated by AI* |