Implement Trie (Prefix Tree)

题目地址：

https://leetcode.com/problems/implement-trie-prefix-tree/description/

题目：

Implement a trie with insert, search, and startsWith methods.

解题思路：

这里就是建立一个Trie Tree。

代码：

public class ImplementTrie {

    /**     * 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);     */
    TrieNode root;

    public ImplementTrie(){
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */    public void insert(String word) {
        if(word == null || word.length() == 0){
            return;
        }
        insertDfs(root, word, 0);
    }

    private void insertDfs(TrieNode root, String word, int pos) {
        if(pos == word.length()){
            root.isLeaf = true;
            return;
        }
        char c = word.charAt(pos);
        if(root.children == null){
            root.children = new TrieNode[26];
        }
        if(root.children[c - 'a'] == null){
            root.children[c - 'a'] = new TrieNode();
        }
        insertDfs(root.children[c - 'a'], word, pos + 1);
    }

    /** Returns if the word is in the trie. */    public boolean search(String word) {
        if(word == null || word.length() == 0){
            return true;
        }
        return searchDfs(root, word, 0);
    }

    private boolean searchDfs(TrieNode root, String word, int pos) {
        if(pos == word.length()){
            return root.isLeaf;
        }
        char c = word.charAt(pos);
        if(root.children == null || root.children[c - 'a'] == null){
            return false;
        }
        return searchDfs(root.children[c - 'a'], word, pos + 1);
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */    public boolean startsWith(String prefix) {
        if(prefix == null || prefix.length() == 0){
            return true;
        }
        return startsWithDfs(root, prefix, 0);
    }

    private boolean startsWithDfs(TrieNode root, String prefix, int pos) {
        if(pos == prefix.length()){
            return true;
        }
        char c = prefix.charAt(pos);
        if(root.children == null || root.children[c - 'a'] == null){
            return false;
        }
        return startsWithDfs(root.children[c - 'a'], prefix, pos + 1);
    }

    public static void main(String[] args){
        ImplementTrie implementTrie = new ImplementTrie();
        implementTrie.insert("ab");
        boolean rst = implementTrie.search("a");
        boolean rst2 = implementTrie.startsWith("a");
        System.out.println(rst2);
    }

}