建设网站遇到问题的解决方案,网页设计与制作课程设计报告shu,小程序登录不上去怎么办,seo优化软件购买#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 前缀树 求解思路 实现代码 运行结果 共勉 题目链接
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
提示
1 word.length, prefix.length 2000 word 和 prefix 仅由小写英文字母组成 insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次 求解思路实现代码运行结果 ⚡ 前缀树 求解思路
前缀树是一种用于快速查询某个字符串或者字符前缀是否存在的数据结构。核心是使用边来代表有无字符使用点来记录是否为单词结尾以及其后续字符串的字符。定义一个TrieNode类end表示有无字符串以当前字符结尾TrieNode[]表示26个TrieNode数组保存了对当前结点而言下一个可能出现的所有字符的链接。插入操作从根结点的子结点开始与 word每一个字符进行匹配如果前缀树上没有对应的字符开始不断new新的结点直到插入完 word 的最后一个字符同时还要将最后一个结点end true表示它是一个单词的末尾。查找操作从根结点的子结点开始一直向下匹配如果出现结点值为空就返回 false如果匹配到了最后一个字符只需判断 node.end即可。前缀操作和查找操作类似只是不需要判断最后一个字符结点的end因为可以匹配到最后一个字符肯定有单词以prefix为前缀。有了基本的思路接下来我们就来通过代码来实现一下。 实现代码
class Trie {class TrieNode {boolean end;TrieNode[] tries new TrieNode[26];}TrieNode root;public Trie() {root new TrieNode();}public void insert(String word) {TrieNode node root;for (int i 0; i word.length(); i) {int index word.charAt(i) - a;if (node.tries[index] null) {node.tries[index] new TrieNode();}node node.tries[index];}node.end true;}public boolean search(String word) {TrieNode node root;for (int i 0; i word.length(); i) {int index word.charAt(i) - a;if (node.tries[index] null) {return false;}node node.tries[index];}return node.end;}public boolean startsWith(String prefix) {TrieNode node root;for (int i 0; i prefix.length(); i) {int index prefix.charAt(i) - a;if (node.tries[index] null) {return false;}node node.tries[index];}return true;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj new Trie();* obj.insert(word);* boolean param_2 obj.search(word);* boolean param_3 obj.startsWith(prefix);*/运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
