http://www.lintcode.com/en/problem/implement-trie/

Example
insert("wang")
insert("lint")
search("code")
>>> false
startsWith("li")
>>> true
startsWith("leet")
>>> false
insert("leet")
search("leet)
>>> true
startsWith("le")
>>> true

写一个字典树，要求有三个功能。 1.insert，插入word到字典树 2.search，查找字典树是否有word 3.startsWith， 查找字典树是否有以word开头的词 例子创建的字典树如下图所示，每个trie node会有一个长度26的数组维护word中下一个字母

         []
        |    \
        l     w
      / |      \
     e  i       a
    /   |        \
   e    n         n
  /     |          \
 t      t           g

    /**
 * Your Trie object will be instantiated and called as such:
 * Trie trie = new Trie();
 * trie.insert("lintcode");
 * trie.search("lint"); will return false
 * trie.startsWith("lint"); will return true
 */


class TrieNode {
    private TrieNode[] children;
    public boolean hasWord;
    // 每一个trie node用children数组存26个字母，表示单词下一个字母组合
    public TrieNode() {
        children = new TrieNode[26];
        hasWord = false;
    }

    public void insert(String word, int index) {
        // 当index到最后一位，把hasword设置为true
        if (index == word.length()) {
            this.hasWord = true;
            return;
        }

        // 拿到当前index字符应在的position
        // 如果为空，我们在数组position处创建新node
        // 然后继续递归下一个字母
        int pos = word.charAt(index) - 'a';
        if (children[pos] == null) {
            children[pos] = new TrieNode();
        }
        children[pos].insert(word, index + 1);
    }

    public TrieNode find(String word, int index) {
        if (index == word.length()) {
            return this;
        }
        // 同样计算每个字符position，如果在字典树中有一个没有找到就返回空
        int pos = word.charAt(index) - 'a';
        if (children[pos] == null) {
            return null;
        }
        return children[pos].find(word, index + 1);
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        // do intialization if necessary
        root = new TrieNode();
    }

    /*
     * @param word: a word
     * @return: nothing
     */
    public void insert(String word) {
        // write your code here
        root.insert(word, 0);
    }

    /*
     * @param word: A string
     * @return: if the word is in the trie.
     */
    public boolean search(String word) {
        // write your code here
        TrieNode node = root.find(word, 0);
        return (node != null && node.hasWord);
    }

    /*
     * @param prefix: A string
     * @return: if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        // write your code here
        TrieNode node = root.find(prefix, 0);
        return node != null;
    }
}