leetcode：208. 实现 Trie (前缀树)

水深无声 2021-09-28 11:16 335阅读 0赞

实现一个 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` 构成的。
 *  保证所有输入均为非空字符串。

class TrieNode {
        boolean isWord;
        TrieNode[] childs;
    
        public TrieNode() {
            isWord = false;
            childs=new TrieNode[26];
        }
    }
    
    class Trie {
        
        /** Initialize your data structure here. */
           TrieNode root;
    
        public Trie() {
            root = new TrieNode();
        }
    
        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            TrieNode r = root;
            //每一个字符进行循环判断向root中插入如果存在则不进行插入在其相应的孩子中进行插入
            for (int i = 0; i < word.length(); i++) {
                //childs中的0-25是字母a-z所以需要char出来然后减去a得到child的下标
                int index = word.charAt(i) - 'a';
                //判断是否已存在存在后进行下一个
                if (r.childs[index] == null) {
                    r.childs[index] = new TrieNode();
                }
                r = r.childs[index];
            }
            //循环完现在r在最后一个字符节点所以设为true表示是一个词而不是前缀
            r.isWord = true;
        }
    
        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
            TrieNode r = root;
            //每一个字符进行循环判断向root中插入如果存在则不进行插入在其相应的孩子中进行插入
            for (int i = 0; i < word.length(); i++) {
                //childs中的0-25是字母a-z所以需要char出来然后减去a得到child的下标
                int index = word.charAt(i) - 'a';
                //判断是否已存在存在后进行下一个
                if (r.childs[index] == null) {
                    return false;
                }
                r = r.childs[index];
            }
            //循环完现在r在最后一个字符节点所以设为true表示是一个词而不是前缀直接诶返回即可
            return r.isWord;
        }
    
        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            TrieNode r = root;
            //每一个字符进行循环判断向root中插入如果存在则不进行插入在其相应的孩子中进行插入
            for (int i = 0; i < prefix.length(); i++) {
                //childs中的0-25是字母a-z所以需要char出来然后减去a得到child的下标
                int index = prefix.charAt(i) - 'a';
                //判断是否已存在存在后进行下一个
                if (r.childs[index] == null) {
                    return false;
                }
                //向下一个节点循环
                r = r.childs[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);
     */