LeetCode 热题 100_实现 Trie (前缀树)（54_208_中等_C++）(图；前缀树；字典树)
@[TOC](LeetCode 热题 100_实现 Trie (前缀树)（54_208）)
题目描述：
Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
输入输出样例：
示例 1：
输入
[“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 次
题解：
解题思路：
思路一（前缀树（字典树））：
1、解决此问题我们需要了解什么是前缀树，了解其树形结构和特性。
例：
从上图中我们可以分析出前缀树的一些特性：
① 树形结构：每个节点代表一个字符，根节点代表空字符串。每一条从根节点到叶子节点的路径代表一个字符串。
②共享前缀：所有具有相同前缀的字符串会共享相同的路径（从根节点到某个节点的路径是相同的）。因此，前缀树适合存储一组具有相同前缀的字符串。
③快速查找：通过字符逐一比对的方式，可以在树中快速找到一个完整的字符串或前缀。
④插入和查找效率：前缀树的查找、插入时间复杂度都为 O(L)，其中 L 是字符串的长度。由于它基于字符逐层匹配，因此比起常规的哈希表等数据结构在某些场景下效率更高，尤其是当需要进行前缀匹配或字典树操作时。
2、具体思路如下：
通过1中的例题可得
① Trie() {} 需要我们根据问题的特性进行树形结构的创建，每个节点代表一个字符，因 a~z 是26个字符，所以我们需要每个节点含有26个指向下一个结点的指针。还需使用一个标志（变量）来存储当前字母是否是单词的最后一个字母。
② 插入单词到前缀树 insert，进行字母插入时，若之前插入过当前字母则跳过，否则将创建节点。若当前字母是单词的最后一个字母，则进行标记。
③ 查找单词是否在前缀树中存在 search，进行逐个字母的判断，若当前字母不在前缀树中则返回false。若单词中的字母都存在前缀树中，还需判断单词的最后一个字母在前缀树中是否被标记，若已标记则返回true，否则返回false。
④ 检查是否有单词以给定的前缀开始 startsWith ，只需逐个字母进行判断，若当前字母不在前缀树中则返回false。若逐个判断匹配成功则返回true（无需进行单词末尾标记判断）
3、复杂度分析：
① 时间复杂度：初始化为 O(1)，其余操作为 O(∣S∣)，其中 ∣S∣ 是每次插入或查询的字符串的长度。插入需逐个字母插入，查询需逐个字母进行判断。
② 空间复杂度：O(∣T∣⋅Σ)，其中 ∣T∣ 为所有插入字符串的长度之和，Σ 为字符集的大小，本题 Σ=26。
代码实现
代码实现（思路一（前缀树（字典树）））：
class Trie {
private:
//子节点的指针数组，大小为26，代表字母a-z
vector<Trie *> children;
//标记当前节点是否是一个单词的结尾
bool isEnd;
// 辅助函数：查找给定前缀路径的最后一个节点
Trie* searchPerfix(string prefix){
// 从根节点开始
Trie* node = this;
for (char ch : prefix)
{
// 将字符转换为0到25的索引（a=0, b=1, ..., z=25）
ch-='a';
// 如果该子节点不存在，返回空，表示前缀不存在
if (node->children[ch] == nullptr) return nullptr;
// 移动到下一个节点
node=node->children[ch];
}
// 返回最后的节点，表示前缀存在
return node;
}
public:
// 构造函数：初始化一个空的Trie树
Trie() : children(26),isEnd(false) {}
// 插入一个单词到Trie树中
void insert(string word) {
// 从根节点开始
Trie* node=this;
for (char ch : word)
{
// 将字符转换为0到25的索引
ch -='a';
// 如果该子节点不存在, 创建一个新节点
if (node->children[ch]==nullptr)
{
node->children[ch]=new Trie();
}
//移动到下一个节点
node=node->children[ch];
}
// 设置单词的结尾
node->isEnd=true;
}
// 查找单词是否存在于Trie树中
bool search(string word) {
//查找单词的路径
Trie *node=this->searchPerfix(word);
// 如果找到路径且是单词结尾，返回true
return node !=nullptr && node->isEnd;
}
// 检查是否存在以给定前缀开头的单词(如果前缀存在，返回true)
bool startsWith(string prefix) {
return this->searchPerfix(prefix)!=nullptr;
}
};
以思路一为例进行调试
#include<iostream>
#include<vector>
using namespace std;
class Trie {
private:
//子节点的指针数组，大小为26，代表字母a-z
vector<Trie *> children;
//标记当前节点是否是一个单词的结尾
bool isEnd;
// 辅助函数：查找给定前缀路径的最后一个节点
Trie* searchPerfix(string prefix){
// 从根节点开始
Trie* node = this;
for (char ch : prefix)
{
// 将字符转换为0到25的索引（a=0, b=1, ..., z=25）
ch-='a';
// 如果该子节点不存在，返回空，表示前缀不存在
if (node->children[ch] == nullptr) return nullptr;
// 移动到下一个节点
node=node->children[ch];
}
// 返回最后的节点，表示前缀存在
return node;
}
public:
// 构造函数：初始化一个空的Trie树
Trie() : children(26),isEnd(false) {}
// 插入一个单词到Trie树中
void insert(string word) {
// 从根节点开始
Trie* node=this;
for (char ch : word)
{
// 将字符转换为0到25的索引
ch -='a';
// 如果该子节点不存在, 创建一个新节点
if (node->children[ch]==nullptr)
{
node->children[ch]=new Trie();
}
//移动到下一个节点
node=node->children[ch];
}
// 设置单词的结尾
node->isEnd=true;
}
// 查找单词是否存在于Trie树中
bool search(string word) {
//查找单词的路径
Trie *node=this->searchPerfix(word);
// 如果找到路径且是单词结尾，返回true
return node !=nullptr && node->isEnd;
}
// 检查是否存在以给定前缀开头的单词(如果前缀存在，返回true)
bool startsWith(string prefix) {
return this->searchPerfix(prefix)!=nullptr;
}
};
int main(int argc, char const *argv[])
{
// 创建一个新的 Trie 对象
Trie trie;
// 插入单词 "apple"
trie.insert("apple");
// 查找单词apple是否存在，返回 True
cout<<trie.search("apple")<<endl;
// 查找单词apple是否存在，返回 False
cout<<trie.search("app")<<endl;
// 查找当前存储的单词中是否存在前缀app，返回 True
cout<<trie.startsWith("app")<<endl;
// 插入单词 "app"
trie.insert("app");
cout<<trie.search("app")<<endl; //查找单词app是否存在，返回 True
return 0;
}
LeetCode 热题 100_实现 Trie (前缀树)（54_208)原题链接
欢迎大家和我沟通交流(✿◠‿◠)
原文地址：https://blog.csdn.net/huayimenghan/article/details/145270298
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！