广州网站推广联盟,新手设计师接单网站,网站开发后期工作包括那两个部分,广州地铁21号线题目 前缀树介绍#xff1a;https://blog.csdn.net/DeveloperFire/article/details/128861092 什么是前缀树 在计算机科学中#xff0c;trie#xff0c;又称前缀树或字典树#xff0c;是一种有序树#xff0c;用于保存关联数组#xff0c;其中的键通常是字符串。与二叉查…题目 前缀树介绍https://blog.csdn.net/DeveloperFire/article/details/128861092 什么是前缀树 在计算机科学中trie又称前缀树或字典树是一种有序树用于保存关联数组其中的键通常是字符串。与二叉查找树不同键不是直接保存在节点中而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀也就是这个节点对应的字符串而根节点对应空字符串。一般情况下不是所有的节点都有对应的值只有叶子节点和部分内部节点所对应的键才有相关的值。 trie 中的键通常是字符串但也可以是其它的结构。trie 的算法可以很容易地修改为处理其它结构的有序序列比如一串数字或者形状的排列。比如bitwise trie 中的键是一串位元可以用于表示整数或者内存地址。trie 树常用于搜索提示。如当输入一个网址可以自动搜索出可能的选择。当没有完全匹配的搜索结果可以返回前缀最相似的可能。
法1迭代实现 class Trie {private Trie[] children;private boolean isEnd;public Trie() {this.children new Trie[26];this.isEnd false;}public void insert(String word) {Trie node this;for (int i 0; i word.length(); i) {char c word.charAt(i);int index c - a;if (node.children[index] null) {node.children[index] new Trie();}node node.children[index];}node.isEnd true;}public boolean search(String word) {Trie node searchPrefix(word);return node ! null node.isEnd true;}public boolean startsWith(String prefix) {Trie node searchPrefix(prefix);return node ! null;}public Trie searchPrefix(String word) {Trie node this;for (int i 0; i word.length(); i) {int index word.charAt(i) - a;if (node.children[index] null) {return null;}node node.children[index];}return node;}
}/*** 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);*/
