https://www.lintcode.com/problem/implement-trie-prefix-tree

Tries.java

class TrieNode {
    boolean isWord;
    HashMap<Character, TrieNode> children;
    
    TrieNode() {
        children = new HashMap<>();
    }
}
    
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
        TrieNode parent = root;
        
        for (int i = 0; i < word.length(); i++) {
            char character = word.charAt(i);
            
            TrieNode node;
            if (parent.children.containsKey(character)) {
                node = parent.children.get(character);
            } else {
                node = new TrieNode();
            }
            
            parent.children.put(character, node);
            parent = node;
        }
        parent.isWord = true;
    }

    /*
     * @param word: A string
     * @return: if the word is in the trie.
     */
    public boolean search(String word) {
        // write your code here
        TrieNode parent = findPrefixNode(word);
        if (parent == null) {
            return false;
        }
        return parent.isWord;
    }

    /*
     * @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
        return findPrefixNode(prefix) != null;
    }
    
    private TrieNode findPrefixNode(String prefix) {
        if (prefix == null) {
            return null;
        }
        
        TrieNode parent = root;
        for (int i = 0; i < prefix.length(); i++) {
            char character = prefix.charAt(i);
            if (!parent.children.containsKey(character)) {
                return null;
            }
            
            TrieNode node = parent.children.get(character);
            parent = node;
        }
        return parent;
    }
}