建站自助,做微信投票的网站5,无锡网站建设公司哪家好,嘉兴网站建设企业网站制作Trie#xff08;发音类似 try#xff09;或者说 前缀树 是一种树形数据结构#xff0c;用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景#xff0c;例如自动补完和拼写检查。
请你实现 Trie 类#xff1a;
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 2000word 和 prefix 仅由小写英文字母组成insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次
解题思路
用到字典树和前缀树的思想字典树指的是结点包含一个子结点数组用一个标记判断是否为一个单词 如果标记为false说明从根节点到当前结点只是一个完整单词的前缀的一部分如果标记为true说明从根节点到当前结点存在一个完整的单词用到字符减去字符a得到该字符的相对索引值再为该索引下的数组元素new 一个 Trie对象用于后面判断该字符是否存在 若该字符转化为索引对应的数组元素值不为空说明该字符存在否则说明该字符不存在
class Trie {private Trie[] children;private boolean isEnd;public Trie(){this.childrennew Trie[26];}public void insert(String word) {Trie headthis;int index-1;for(int i0;iword.length();i){indexword.charAt(i)-a;if(head.children[index]null){head.children[index]new Trie();}headhead.children[index];}head.isEndtrue;}public boolean search(String word) {Trie headthis;int index-1;for(int i0;iword.length();i){indexword.charAt(i)-a;if(head.children[index]null)return false;headhead.children[index];}if(head.isEnd)return true;return false;}public boolean startsWith(String prefix) {Trie headthis; int index-1;for(int i0;iprefix.length();i){indexprefix.charAt(i)-a;if(head.children[index]null)return false;headhead.children[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);*/
