[LintCode] Implement Trie 实现字典树
实现 字典 lintcode Trie Implement
2023-09-11 14:21:39 时间
Implement a trie with insert, search, and startsWith methods.
Have you met this question in a real interview?
Example
Note
You may assume that all inputs are consist of lowercase letters a-z.
LeetCode上的原题,请参见我之前的博客Implement Trie (Prefix Tree) 实现字典树(前缀树)。
/** * Your Trie object will be instantiated and called as such: * Trie trie; * trie.insert("lintcode"); * trie.search("lint"); will return false * trie.startsWith("lint"); will return true */ class TrieNode { public: // Initialize your data structure here. TrieNode *child[26]; bool isWord; TrieNode(): isWord(false) { for (auto & a : child) a = NULL; } }; class Trie { public: Trie() { root = new TrieNode(); } // Inserts a word into the trie. void insert(string word) { TrieNode *p = root; for (auto &a : word) { int i = a - 'a'; if (!p->child[i]) p->child[i] = new TrieNode(); p = p->child[i]; } p->isWord = true; } // Returns if the word is in the trie. bool search(string word) { TrieNode *p = root; for (auto &a : word) { int i = a - 'a'; if (!p->child[i]) return false; p = p->child[i]; } return p->isWord; } // Returns if there is any word in the trie // that starts with the given prefix. bool startsWith(string prefix) { TrieNode *p = root; for (auto &a : prefix) { int i = a - 'a'; if (!p->child[i]) return false; p = p->child[i]; } return true; } private: TrieNode* root; };
相关文章
- Android版俄罗斯方块的实现
- 推荐12个漂亮的 CSS3 按钮实现方案
- 基于SpringCloud实现Shard-Jdbc的分库分表模式,数据库扩容方案
- 字典树的实现
- 六种方式实现 springboot 项目 启动预加载
- uni-app - 用户点击图像放大预览功能 / 支持左右滑动与手指手势放大缩小图片(支持单图与多图、实现手机查看大图全屏预览功能),类似微信查看图片的效果,支持 App、H5、小程序等全端兼容!
- 查找树-- 基于后缀字典树实现字符串的模式查找
- 基于Redis的布隆过滤器的实现
- 欧拉计划第十一题--java实现
- 【转】HashMap实现原理分析
- 【C++】:想知道如何实现互译字典吗?来看二叉搜索树
- knn算法的c语言实现
- Java经典实例:进阶版堆栈实现,支持任何对象类型
- 转: oracle 存储过程 执行动态 实现sql
- netty系列之:HashedWheelTimer一种定时器的高效实现
- 【虚拟仿真】Unity3D中实现InputField组件表格Tab或者Enter换行实现
- 【python】dict多种方法实现去除字典value为0 的元素