Leetcode刷题java之208. 实现 Trie (前缀树)（一天一道编程题之四十六天）

待我称王封你为后i 2023-07-21 11:19 123阅读 0赞

在这顺便说一下AC自动机，KMP是判断一个字符串中是否有另一个字符串，AC自动机是判断多个单词是否在一篇文章中出现过。它基于字典树trie树和KMP算法，在字典树的基础上，加了一个失败指针，失败指针按照KMP算法的思想进行跳转，跳转到与后缀相同的前缀。

执行结果：

通过

显示详情

执行用时 :56 ms, 在所有 Java 提交中击败了47.39% 的用户

内存消耗 :49.1 MB, 在所有 Java 提交中击败了100.00%的用户

题目：

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

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

说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。  
保证所有输入均为非空字符串。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

参考：[https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode/][https_leetcode-cn.com_problems_implement-trie-prefix-tree_solution_shi-xian-trie-qian-zhui-shu-by-leetcode]

代码：

时间复杂度，构建o(n),查找o（k），n为构建时所有字符串的长度，k为查找字符串的长度。

class TrieNode
    {
        //创建一个大小为26的TrieNode数组，表示当前节点的孩子节点。
        //对应位置有节点，说明就有对应位置索引的字母
        private TrieNode[] links;
        private int R=26;
        private boolean isEnd=false;
        public TrieNode()
        {
            links=new TrieNode[R];
        }
        public boolean containsKey(char c)
        {
            return links[c-'a']!=null;
        }
        public TrieNode get(char c)
        {
            return links[c-'a'];
        }
        public void put(char c,TrieNode node)
        {
            links[c-'a']=node;
        }
        public void setEnd()
        {
            isEnd=true;
        }
        public boolean isEnd()
        {
            return isEnd;
        }
    }
    class Trie {
        private TrieNode root;
        /** Initialize your data structure here. */
        public Trie() {
            root=new TrieNode();
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
            TrieNode node=root;
            for(int i=0;i<word.length();i++)
            {
                char temp=word.charAt(i);
                if(!node.containsKey(temp))
                {
                    node.put(temp,new TrieNode());
                }
                node=node.get(temp);
            }
            node.setEnd();
        }
        
        private TrieNode searchPrefix(String word)
        {
            TrieNode node=root;
            for(int i=0;i<word.length();i++)
            {
                char c=word.charAt(i);
                if(node.containsKey(c))
                {
                    node=node.get(c);
                }else
                {
                    return null;
                }
            }
            return node;
        }
        //当z返回的节点不为空，并且是末尾了，那么它就是这个单词
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            TrieNode node=searchPrefix(word);
            return node!=null&&node.isEnd();
        }
        //如果返回的节点不为空，说明前面的就都匹配了，说明有这个索引
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            TrieNode node=searchPrefix(prefix);
            return node!=null;
        }
    }
    
    /**
     * 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);
     */

[https_leetcode-cn.com_problems_implement-trie-prefix-tree_solution_shi-xian-trie-qian-zhui-shu-by-leetcode]: https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode/