Trie.java

public class Trie {
    final static int ALPHABET_SIZE = 26; 
    Trie[] children;

    public Trie() {
        this.children = new Trie[ALPHABET_SIZE];
    }

    // return true if the word added is new.
    public boolean insert(String s) {
        if (s == null || s.equals("")) {
            return false;
        }
        final int index = s.charAt(0) - 'a';
        if (index < 0 || index >= ALPHABET_SIZE) {
            throw new IllegalArgumentException("String contains characters outside the range [a-z]");
        }

        if (children[index] != null) {
            return children[index].insert(s.substring(1));
        } else {
            children[index] = new Trie();
            children[index].insert(s.substring(1));

            return true;
        }
    }

    public boolean contains(String word) {
        if (word == null) {
            return false;
        }

        if (word.equals("")) {
            return true;
        } else {
            final int index = word.charAt(0) - 'a';
            if (children[index] == null) {
                return false;
            } else {
                final String tail = word.substring(1);
                return children[index].contains(tail);
            }
        }
    }
}