字典树 (前缀树)

相关源文件

• problems/1032.stream-of-characters.md
• problems/208.implement-trie-prefix-tree.md
• problems/211.add-and-search-word-data-structure-design.md
• problems/212.word-search-ii.md
• problems/472.concatenated-words.md
• problems/820.short-encoding-of-words.md
• thinkings/trie.md

本文档提供了对 LeetCode 存储库中实现和使用的 Trie（前缀树）数据结构的全面概述。它涵盖了 Trie 的基本概念、实现细节以及在解决各种算法问题中的实际应用。

Trie 是一种专门的树状数据结构，用于高效检索字符串数据集中的键。有关二叉搜索树等其他树结构的信息，请参阅 树与图。

1. 什么是 Trie？

Trie，也称为前缀树，是一种树状数据结构，可实现字符串的高效存储和检索。“Trie”这个名字来源于“retrieval”（发音为“try”）。Trie 中的每个节点代表一个字符，从根到标记节点的路径代表完整的单词。

Trie 的关键特征

• 根节点代表空字符串
• 每个节点存储一个字符，并有多个子节点（每个可能的字符对应一个）
• 共享公共前缀的单词在树中共享公共节点
• 使用特殊标记来指示单词的结束

来源：thinkings/trie.md3-12 thinkings/trie.md19-25

1.1 Trie 的可视化表示

此图表示一个包含单词“oath”、“oar”、“he”、“her”、“god”、“good”的 Trie。粉红色（或标记）节点表示单词的结束。

来源：thinkings/trie.md69-72

2. 基本结构和操作

2.1 节点结构

在存储库实现中，Trie 节点通常包含

1. 一个存储字符的值字段
2. 一个子节点数组/映射以存储子节点
3. 控制字段，例如 isWord（标记单词结束）、count（以此节点结束的单词数）和 preCount（以此为前缀的单词数）

来源：thinkings/trie.md27-33 thinkings/trie.md34-49

2.2 核心操作

Trie 数据结构支持三个主要操作

1. 插入：将新单词添加到 Trie 中
2. 搜索：检查单词是否存在于 Trie 中
3. StartsWith：检查 Trie 中的任何单词是否具有给定的前缀

操作	描述	时间复杂度
插入	逐个字符将单词添加到 Trie	O(word 的长度)
搜索	检查 Trie 中是否存在完整的单词	O(word 的长度)
StartsWith	检查 Trie 中是否存在任何具有给定前缀的单词	O(prefix 的长度)

来源：thinkings/trie.md66-67 thinkings/trie.md79-81 thinkings/trie.md240-244

3. 实现细节

3.1 插入过程

将单词插入 Trie 时，我们从根开始，对每个字符执行以下步骤

1. 检查当前字符是否存在于当前节点的子节点中
2. 如果不存在，则为该字符创建一个新节点
3. 移动到子节点
4. 增加该节点的 preCount（前缀计数）
5. 处理完所有字符后，通过增加其 count 来将最后一个节点标记为单词结束

来源：thinkings/trie.md66-76 thinkings/trie.md101-115

3.2 搜索过程

搜索过程遵循以下步骤

1. 从根节点开始
2. 对于单词中的每个字符
   • 如果在当前节点的子节点中找不到该字符，则返回 false
   • 移动到子节点
3. 处理完所有字符后，检查当前节点是否被标记为单词结束
4. 如果它是单词结束，则返回 true，否则返回 false

来源：thinkings/trie.md79-80 thinkings/trie.md117-130

3.3 不同语言的实现

该存储库提供了多种编程语言的 Trie 实现

Python实现

来源：thinkings/trie.md164-199

Java 实现

Java 实现使用大小为 26 的数组作为子节点，假定只包含小写英文字母

来源：thinkings/trie.md92-158

JavaScript 实现

JavaScript 实现使用对象属性作为子节点

来源：thinkings/trie.md204-237

4. 应用和用例

4.1 主要用例

Trie 在涉及字符串操作的场景中特别有效

1. 基于前缀的搜索：查找具有给定前缀的所有单词（自动补全）
2. 精确字符串匹配：检查字符串是否存在于数据集中
3. 拼写检查：为拼写错误的单词建议修正
4. 最长前缀匹配：在一组字符串中查找最长的匹配前缀

Trie 的主要优势在于它们能够利用公共前缀来优化字符串操作，有效地以空间换取时间效率。

来源：thinkings/trie.md9-11 thinkings/trie.md252-259 thinkings/trie.md262-270

4.2 与 LeetCode 问题的关联

Trie 数据结构用于解决存储库中的各种 LeetCode 问题

问题	问题编号	Trie 的应用
实现 Trie	208	具有标准操作的基本 Trie 实现
添加和搜索单词	211	支持搜索中'.'通配符字符的 Trie
单词搜索 II	212	使用 Trie 高效地在二维网格中搜索单词
连接词	472	使用 Trie 查找由其他单词组成的单词
单词短编码	820	使用 Trie 压缩单词列表（后缀匹配）
字符流	1032	使用 Trie 处理字符流

来源：thinkings/trie.md276-286

5. 高级概念和优化

5.1 反向 Trie（后缀树）

对于某些问题，例如单词压缩（问题 820），反向 Trie 或后缀树方法可能更有效

1. 不正常插入单词，而是反向插入
2. 这允许高效地检查一个单词是否是另一个单词的后缀
3. 在需要后缀匹配的问题中特别有用

来源：problems/820.short-encoding-of-words.md42-48 problems/1032.stream-of-characters.md86

5.2 内存优化

多种技术可以减少 Trie 的内存占用

1. 压缩 Trie：将具有单一子节点的节点合并为一个节点
2. 选择性插入：在某些问题中，如果单词不影响结果，我们可以避免插入它们
3. 使用 Map 而非数组：当字符集较大或稀疏时，使用 Map 作为子节点

来源：problems/472.concatenated-words.md73-89

6. 复杂度分析

6.1 时间复杂度

操作	时间复杂度	备注
插入	O(键的长度)	其中键是要插入的单词
搜索	O(键的长度)	其中键是要搜索的单词
StartsWith	O(prefix 的长度)	其中 prefix 是要搜索的前缀
从单词构建 Trie	O(Σ单词的长度)	所有单词长度的总和

6.2 空间复杂度

最坏情况下的空间复杂度为 O(m^n)，其中

• m 是字符集的大小（例如，小写英文字母为 26）
• n 是最长字符串的长度

在实践中，由于共享前缀，所需空间通常远小于此。

来源：thinkings/trie.md240-244

7. 存储库中的相关问题

存储库包含几个使用 Trie 的问题

1. Implement Trie (Prefix Tree) - 基本的 Trie 实现
2. 添加和搜索单词 - 数据结构设计 - 支持通配符搜索的Trie
3. 单词搜索 II - 使用Trie在网格中搜索单词
4. 连接词 - 查找由其他单词组成的单词
5. 单词的简短编码 - 压缩单词列表
6. 字符流 - 处理字符流

来源：thinkings/trie.md276-286

8. 总结

Tries 是一种强大的数据结构，用于高效的字符串操作，特别是当处理大量具有共同前缀的字符串时。Tries 的关键原则是以空间换时间，这使其在自动完成、拼写检查和各种字符串匹配问题等应用中具有无价的价值。

在实现 Trie 时，应考虑问题的具体要求，例如标准 Trie、反向 Trie 还是具有附加功能（如通配符搜索）的 Trie 最合适。

来源: thinkings/trie.md289-296