题目链接

/**

        Trie前缀树基本结构:

                        (多叉单词查找树)每个Trie中包含一个Trie数组与一个结束标识

                        Trie[] children Trie数组,每个节点都可存放一个Trie,其索引代表该节点对应的字符。

                        boolean isEnd 结束标识, 代表当前节点是否是一个完整单词的结尾巴

        前缀树insert流程:

                        计算第一个字符的索引位置,判断根节点的Trie节点数组中是否已有该字符(对应位置不为null,有Trie节点)

                        若没有则创建新的节点赋值到对应位置,有则迭代Trie节点与字符按上述流程继续处理

                        按上述流程迭代字符与Trie节点,直到处理到最后一个字符,将isEnd设置为true

         前缀树search流程:

                        计算第一个字符的索引位置,判断根节点的Trie节点数组是否已有该字符(对应位置不为null,有Trie节点)

                        有则迭代字符与Trie节点,重复上述流程;无则返回false

                        直到迭代到最后一个字符,判断isEnd是否为true,若不为true也返回false(只是在某个单词中出现了相同的部分)

        前缀树startsWith流程:

                        计算第一个字符的索引位置,判断根节点的Trie节点数组是否已有该字符(对应位置不为null,有Trie节点)

                        有则迭代字符与Trie节点,重复上述流程;无则返回false

                        直到最后一个字符也存在(只判断有无该前缀,无需判断isEnd)

        可抽取的公共方法:(查找前缀)

                        计算第一个字符的索引位置,判断根节点的Trie节点数组是否已有该字符(对应位置不为null,有Trie节点)

                        有则迭代字符与Trie节点,重复上述流程; 返回最后一个节点

                        search搜寻到最后一个节点判断其isEnd即可

                        startsWith搜寻到最后一个节点判断是否为空即可

*/

class Trie {/**Trie前缀树基本结构:(多叉单词查找树)每个Trie中包含一个Trie数组与一个结束标识Trie[] children Trie数组,每个节点都可存放一个Trie,其索引代表该节点对应的字符。boolean isEnd 结束标识, 代表当前节点是否是一个完整单词的结尾巴前缀树insert流程:计算第一个字符的索引位置,判断根节点的Trie节点数组中是否已有该字符(对应位置不为null,有Trie节点)若没有则创建新的节点赋值到对应位置,有则迭代Trie节点与字符按上述流程继续处理按上述流程迭代字符与Trie节点,直到处理到最后一个字符,将isEnd设置为true前缀树search流程:计算第一个字符的索引位置,判断根节点的Trie节点数组是否已有该字符(对应位置不为null,有Trie节点)有则迭代字符与Trie节点,重复上述流程;无则返回false直到迭代到最后一个字符,判断isEnd是否为true,若不为true也返回false(只是在某个单词中出现了相同的部分)前缀树startsWith流程:计算第一个字符的索引位置,判断根节点的Trie节点数组是否已有该字符(对应位置不为null,有Trie节点)有则迭代字符与Trie节点,重复上述流程;无则返回false直到最后一个字符也存在(只判断有无该前缀,无需判断isEnd)可抽取的公共方法:(查找前缀)计算第一个字符的索引位置,判断根节点的Trie节点数组是否已有该字符(对应位置不为null,有Trie节点)有则迭代字符与Trie节点,重复上述流程; 返回最后一个节点search搜寻到最后一个节点判断其isEnd即可startsWith搜寻到最后一个节点判断是否为空即可*///节点数组private Trie[] children;//结束标识boolean isEnd;//公共方法private Trie searchPrefix(String prefix) {Trie node = this; //读取当前节点for(char ch : prefix.toCharArray()) {//计算当前字符索引位置int index = ch - 'a'; //迭代node = node.children[index];if(node == null) { //若为空代表已中断直接结束即可break;}}return node;}public Trie() {children = new Trie[26]; //一共26个字符isEnd = false; //结束标识默认为false}public void insert(String word) {Trie node = this; //读取当前节点for(char ch : word.toCharArray()) {//计算当前字符索引位置int index = ch - 'a'; //若当前节点的Trie节点数组中不存在该字符if(node.children[index] == null) {Trie son = new Trie();node.children[index] = son;}//迭代(存在则直接迭代)node = node.children[index]; }node.isEnd = true; //设置结束标识}public boolean search(String word) {//一直读取到最后一个字符 判断isEnd即可Trie node = searchPrefix(word);if(node != null) {return node.isEnd;}return false; }public boolean startsWith(String prefix) {//一直读取到最后一个字符 判断是否为空即可if(searchPrefix(prefix) != null) {return true;}return false;}
}/*** 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);*/