【刷题-LeetCode】208. Implement Trie (Prefix Tree)
2024-09-25 12:17:06
- Implement Trie (Prefix Tree)
Implement a trie with insert
, search
, and startsWith
methods.
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
Note:
- You may assume that all inputs are consist of lowercase letters
a-z
. - All inputs are guaranteed to be non-empty strings.
解
class trie_node{
public:
vector<trie_node*>child; // 根据当前字符选取下一个节点,如果当前字符是a,接下来就往child['a']的分支走
bool isWord; // 表明到达该节点时,是否包含了一个完整的单词
// 构造函数
trie_node(): isWord(false), child(26, NULL){}
// 析构函数
~trie_node(){
for(auto &c : child)delete c;
}
};
class Trie {
public:
trie_node* root;
/** Initialize your data structure here. */
// 构造函数
Trie() {
root = new trie_node();
}
/** Inserts a word into the trie. */
void insert(string word) {
trie_node *cur = root;
for(int i = 0; i < word.size(); ++i){
int idx = word[i] - 'a';
if(cur->child[idx] == NULL){
cur->child[idx] = new trie_node();
}
cur = cur->child[idx];
}
cur->isWord = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
trie_node *cur = root;
for(auto ch : word){
int idx = ch - 'a';
if(cur->child[idx] == NULL)return false;
cur = cur->child[idx];
}
return cur->isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
trie_node *cur = root;
for(auto ch : prefix){
int idx = ch - 'a';
if(cur->child[idx] == NULL)return false;
cur = cur->child[idx];
}
return true;
}
};
/**
* 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);
*/
最新文章
- C#通用类Helper整理
- [充电]C++ string字符串替换
- HQueue:基于HBase的消息队列
- mysql in 查询优化
- java环境变量完整版
- seafile修改
- Android中文乱码彻底解决
- InnoDB概览
- Android与JS混编(js调用java)
- Ubuntu纯字符界面的一些设置
- vue客户端渲染首屏优化之道
- windows下用c++调用caffe做前向
- 6.1 集合和映射--集合Set->;底层基于二叉搜索树实现
- cf 20190307 Codeforces Round #543 (Div. 2, based on Technocup 2019 Final Round)
- python 贝叶斯算法
- C#基础第二天-作业答案-九九乘法表-打印星星
- Oracle 监听服务启动不了
- RAC配置笔记
- 我爱Markdown (1)
- PLL各种问题,关于倍频
热门文章
- Linux下c++之常见错误代码errno(退而结网法)
- 【LeetCode】1007. Minimum Domino Rotations For Equal Row 解题报告(Python)
- 【LeetCode】976. Largest Perimeter Triangle 解题报告(Python)
- 【LeetCode】598. Range Addition II 解题报告(Python)
- How Many Sets I(zoj3556)
- 基于React和Node.JS的表单录入系统的设计与实现
- 实现golang io.Writer支持按照天为单位分割日志
- HITCON 2019 Lost Modular again writeup
- Java初学者作业——声明变量对个人信息进行输入和输出
- 涂鸦智能 dubbo-go 亿级流量的实践与探索