当前位置:网站首页>力扣208,实现Trie(前缀树)
力扣208,实现Trie(前缀树)
2022-08-09 07:02:00 【瀛台夜雪】
力扣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 。
输入输出样例
输入
["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
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/implement-trie-prefix-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
tips
1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次
解法:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//Trie,又称为前缀树或字典树,是一颗有限数
//指向子节点的指针数组next.即小写英文字母的数量
//isend,表示该结点是否为字符串的结尾
class Trie{
private:
bool isEnd;
Trie *next[26];
public:
Trie()
{
isEnd=false;
//memset 将某一块内存中的全部设置为指定的值
memset(next,0,sizeof(next));
}
//首先从根节点的子节点开始和word第一个字符进行匹配,一直匹配到前缀链上没有对应的字符
//此时不断开辟新的结点,直到插入完word的最后一个字符,并将最后一个结点的isend=true, 表明是但此的末尾
void insert(string word)
{
Trie*node=this;
for(char c:word)
{
if(node->next[c-'a']==NULL)
{
node->next[c-'a']=new Trie();
}
node=node->next[c-'a'];
}
node->isEnd=true;
}
//从根结点的子节点开始,一直向下进行匹配,如果出现结点值为空就返回false,如果
//待搜索的结点已经到最后一个值,那么只需看最后一个结点的isEnd的状态即可
bool search(string word)
{
Trie*node=this;
for(char c:word)
{
node=node->next[c-'a'];
if(node==NULL)
{
return false;
}
}
return node->isEnd;
}
//和查找的函数类似,但是最后判断无需判断最后一个结点的isend,因为是前缀
bool startsWith(string prefix)
{
Trie *node=this;
for(char c:prefix)
{
node=node->next[c-'a'];
if(node==NULL)
{
return false;
}
}
return true;
}
};
int main()
{
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
}
边栏推荐
猜你喜欢
随机推荐
高项 01 信息化与信息系统
AD picture PCB tutorial 20 minutes clear label shop operation process, copper network
The water problem of leetcode
composer 内存不足够
db.sqlite3 has no "as Data Source" workaround
查看日志常用命令
list与string转换
浅识微服务架构
imageio读取.exr报错 ValueError: Could not find a backend to open `xxx.exr‘ with iomode `r`
洛谷P1110 报表统计 multiset stl好题
longest substring without repeating characters
AD的library中 库文件后缀有.intlib .schlib .pcblib 的区别
分布式理论
单例 DCL(double check lock) 饱汉模式和饿汉模式
codeforces Valera and Elections (这思维题是做不明白了)
高项 03 项目立项管理
TCP段重组PDU
eyb:Redis学习(2)
DSP+ARM+FPGA高速PCIE/千兆网口信号仿真介绍
【Docker】Docker安装MySQL