leetcode 208. 实现 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。
基本做法：unordered_set<string>存储，前缀通过find实现
适用于 单词长度较小
class Trie {
public:
unordered_set<string> dp;
Trie() {
}
void insert(string word) {
if(!dp.count(word))
{
dp.insert(word);
}
}
bool search(string word) {
if(dp.count(word))
{
return true;
}
else return false;
}
bool startsWith(string prefix) {
for(auto ie:dp)
{
if(ie.find(prefix)==0)
{
return true;
}
}
return false;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/优点：插入，和查询的时间复杂度为O(1),内存占用小
缺点：多次前缀查询性能较低，时间复杂度为O(N*len) len为单词长度
26叉树实现
我们在Trie类种定义了一个26字母next表
适用于需要多次使用到前缀查询
字符插入
//当我们插入 apple对象时
当前Tire next全为空
第一个字符为a
那我们 将next[0]创建好
第二个字符 为p
那我们创建之前next[0]指向的next['p'-'a']
然后依次类推知道字符遍历完毕 我们就将这个字符插入到这个26叉数中 并且有利于前缀查询
void insert(string word)
{
auto temp=this;
for(auto c:word)
{
c-='a';
if(!temp->next[c]) temp->next[c]=new Trie();
temp=temp->next[c];
}
temp->is_end=true; //记录当前位置是一个单词的尾 和前缀区分开来以便serach
}查找辅助函数
Trie* find_(string prefix)
{
auto temp=this;
for(auto c:prefix)
{
c-='a';
if(temp->next[c]==nullptr) //字符未遍历完但遇空 则表示没有相应的单词
{
return nullptr;
}
temp=temp->next[c];
}
return temp; //返回prefix单词最后一个字符的next表
}前缀查找prefix
找到前缀prefix 直接 return find_(predix)!=nullptr;
单词查找word
我们需要判断word最后一个字符的next表是否是 单词尾部 否则这个只是一个前缀 而不是单词本身
return find_(word)!=nullptr&&find_(wrod)->is_end==true;
完整代码：
class Trie {
public:
vector<Trie*> next;
bool is_end;
Trie():next(26,nullptr),is_end(false){
}
Trie* find_(string prefix)
{
auto temp=this;
for(auto c:prefix)
{
c-='a';
if(temp->next[c]==nullptr)
{
return nullptr;
}
temp=temp->next[c];
}
return temp;
}
void insert(string word) {
auto temp=this;
for(auto c:word)
{
c-='a';
if(!temp->next[c]) temp->next[c]=new Trie();
temp=temp->next[c];
}
temp->is_end=true;
}
bool search(string word) {
return find_(word)&&find_(word)->is_end==true;
}
bool startsWith(string prefix) {
return find_(prefix)!=nullptr;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/ 缺点：内存占用较高 单词的每一个字符都有next表
优点：前缀查询快，单词查询较快，查询，插入时间复杂度均为O(len) len为单词长度
原文地址：https://blog.csdn.net/weixin_72492465/article/details/144009120
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！