原题链接🔗：实现 Trie (前缀树)
难度：中等⭐️⭐️
题目
Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
示例：
输入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 True
trie.search(“app”); // 返回 False
trie.startsWith(“app”); // 返回 True
trie.insert(“app”);
trie.search(“app”); // 返回 True
提示：
- 1 <= word.length, prefix.length <= 2000
- word 和 prefix 仅由小写英文字母组成
- insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次
前缀树
前缀树，又称Trie树（发音为“try”），是一种用于存储字符串集合的数据结构，它允许快速检索和插入字符串，以及对字符串前缀的查询。前缀树的每个节点代表一个字符串的前缀，并且每个节点的子节点代表在该前缀基础上增加一个字符的所有可能的扩展。
- 前缀树的特点：
- 空间效率：对于有大量公共前缀的字符串集合，前缀树可以节省存储空间。
- 时间效率：插入和搜索操作的时间复杂度通常为O(m)，其中m是字符串的长度。
- 动态集合：前缀树可以动态地插入和删除字符串，适用于需要频繁更新的场景。
- 前缀树的基本操作：
- 插入：将一个字符串插入树中，从根节点开始，逐字符向下，如果字符对应的子节点不存在，则创建新节点。
- 搜索：搜索一个字符串是否存在于树中，从根节点开始，逐字符向下，如果某个字符的子节点不存在，则搜索失败。
- 前缀搜索：检查是否存在以某个字符串为前缀的任何字符串，与搜索操作类似，但不需要检查最后一个节点的结束标志。
- 删除：从树中删除一个字符串，需要递归地删除节点，同时确保不删除其他字符串的公共前缀节点。
- 前缀树的应用场景：
- 自动补全：在搜索引擎或文本编辑器中，根据用户输入的前缀快速提供补全建议。
- 拼写检查：检查用户输入的单词是否拼写正确，并提供正确的拼写建议。
- IP路由：在网络中，使用最长前缀匹配来确定数据包的路由路径。
- 基因序列分析：在生物信息学中，用于快速匹配和检索基因序列。
题解
- 解题思路：
Trie（前缀树）是一种用于快速检索字符串数据集中的键的树形数据结构。它是一种特殊的树，其中每个节点代表一个字符，并且从根到某一节点的路径表示一个字符串。Trie树常用于实现自动补全、拼写检查等功能。
以下是实现Trie树的基本步骤和解题思路：
定义Trie节点：
- 每个Trie节点通常包含一个字符集合或一个布尔值来表示单词的结束，以及指向子节点的指针。
初始化Trie：
- 创建一个根节点，它不包含任何字符，但可以作为所有单词的起点。
插入操作：
- 从根节点开始，对于要插入的字符串中的每个字符：
- 如果字符对应的子节点不存在，则创建一个新的子节点。
- 将当前节点移动到对应的子节点。
搜索操作：
- 从根节点开始，对于要搜索的字符串中的每个字符：
- 如果字符对应的子节点存在，则继续搜索。
- 如果不存在，则返回搜索失败。
前缀搜索：
- 类似于搜索操作，但是只关心字符串的前缀是否存在。
删除操作（可选）：
- 根据需要实现删除单词的功能，这通常涉及到删除节点，并且需要处理节点的引用计数。
自动补全功能（可选）：
- 给定一个前缀，返回所有以该前缀开始的字符串。
- c++ demo：
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
class Trie {
private:
vector<Trie*> children;
bool isEnd;
Trie* searchPrefix(string prefix) {
Trie* node = this;
for (char ch : prefix) {
ch -= 'a';
if (node->children[ch] == nullptr) {
return nullptr;
}
node = node->children[ch];
}
return node;
}
public:
Trie() : children(26), isEnd(false) {}
void insert(string word) {
Trie* node = this;
for (char ch : word) {
ch -= 'a';
if (node->children[ch] == nullptr) {
node->children[ch] = new Trie();
}
node = node->children[ch];
}
node->isEnd = true;
}
bool search(string word) {
Trie* node = this->searchPrefix(word);
return node != nullptr && node->isEnd;
}
bool startsWith(string prefix) {
return this->searchPrefix(prefix) != nullptr;
}
};
int main() {
Trie trie;
trie.insert("apple");
std::cout << trie.search("apple") << std::endl; // 返回 1
std::cout << trie.search("app") << std::endl; // 返回 0
std::cout << trie.startsWith("app") << std::endl; // 返回 1
return 0;
}
- 输出结果：
1
0
1
- 代码仓库地址：Trie
