Trie.java

class Trie {
    public static void main(String[] args) {
        String s = "tttt";
        Trie t = new Trie();
        t.insert(s);
        t.insert("ttt");
        System.out.println(t.startsWith("tt"));

    }

    class Node {
        Node[] children = new Node[26];
        boolean isCompleted;
    }

    private Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String s) {
        Node node = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new Node();
            }
            node = node.children[c - 'a']; // moves pointer down.
        }
        node.isCompleted = true;
    }

    public boolean search(String word) {
        Node node = searchNode(word);
        if (node == null) {
            return false;
        }
        return node.isCompleted;
    }

    public boolean startsWith(String prefix) {
        Node node = searchNode(prefix);
        if (node == null) {
            return false;
        }
        return true;
    }

    public Node searchNode(String s) {
        Node node = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (node.children[c - 'a'] == null) {
                return null;
            } else {
                node = node.children[c - 'a'];
            }
        }
        return node;
    }

}