208. Implement Trie (Prefix Tree)

Trie is essentially a 26 fork tree. besides root node, each node in the tree represent a character from a-z. If the path from root node to current node form a valid word, the current node is a terminal node. So long as we figure it out, the implementation is easy as the following shows:

class Trie {
    boolean isTerminal = false;
    Trie array[] = new Trie[26];
    
    /** Initialize your data structure here. */
    public Trie() {
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        if( !search(word) ){
            Trie trie = this;
            for(int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                if( trie.array[index] == null )
                    trie.array[index] = new Trie();
                trie = trie.array[index];
            }
            trie.isTerminal = true;
        }
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Trie trie = help(word);
        return trie != null && trie.isTerminal;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return help(prefix) != null;
    }
    
    public Trie help(String str) {
        Trie trie = this;
        for(int i = 0; i < str.length(); i++) {
            int index = str.charAt(i) - 'a';
            if( trie.array[index] == null )
                return null;
            trie = trie.array[index];
        }
        return trie;
    }
}