208. Implement Trie (Prefix Tree).java

与hashtable和binary tree比较，Trie的好处：
1. hashtable的size很大之后，会有很多collision，时间可能至O(n)-n为要插入的key的number
2. binary tree中查找，时间为O(mlongn)
3. Trie将很多相同prefix的key存在一起，空间上小鱼hashtable，时间只有O(m）-m为key的长度

此题先定义TrieNode，再定义Trie Tree
TrieNode两个变量：TrieNode[26] children存所有的节点link（如：节点下面有3个分支，分别连字母l，k，t，那么children[l]!=null,children[k]!=null……）
                boolean isEnd 表示是否为单词的结尾。如果值为false表示这只是prefix，并无法形成word
Trie：定义好root即可
insert(word):遍历word每个字符，如果存在这个link，就继续向下找；如果不存在就创建一个新的；结尾isEnd设为true
search(word):遍历word每个字符，如果一旦不存在(null),return false；如果存在就一直往下找。return时注意是否isEnd为true，才表示是单词，否则只是个prefix
startWith(prefix):和上面思路一样，唯一结尾的时候不需要看isEnd
                                                
class TrieNode{
    TrieNode[] children;
    boolean isWordEnd;
    public TrieNode() {
        children = new TrieNode[26];
        isWordEnd = false;
    }
}

public class Trie{
    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 ch = word.charAt(i);
            int index = ch - 'a';
            if(node.children[index] == null){
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isWordEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = root;
        for(int i = 0; i < word.length(); i++){
            char ch = word.charAt(i);
            int index = ch - 'a';
            if(node.children[index] == null){
                return false;
            }
            node = node.children[index];
        }
        return node != null && node.isWordEnd;
        
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for(int i = 0; i < prefix.length(); i++){
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if(node.children[index] == null){
                return false;
            }
            node = node.children[index];
        }
        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);
 */