Implement a Trie (insert, search, startsWith).

Problem. Implement a Trie (prefix tree) supporting three operations: insert(word), search(word) — returns true only if the exact word was inserted — and startsWith(prefix) — returns true if any inserted word has that prefix.

The structure

Each node holds links to children (one per next character) and a flag marking whether a complete word ends at that node. The flag is what distinguishes search from startsWith: searching for "car" must fail if you only ever inserted "card", even though the car path exists.

Two children layouts

• TrieNode[26] — O(1) child access, ideal for a fixed lowercase a–z alphabet, but R pointers per node (mostly null).
• Map<Character, TrieNode> — pays only for children that exist, handles any alphabet (Unicode, mixed case), at the cost of hashing per step.

Both give the same Big-O. Below is the map version (general, the one to default to in an interview unless the alphabet is fixed and small); the array variant is noted after.

class Trie {
    private static class Node {
        Map<Character, Node> children = new HashMap<>();
        boolean isWord = false;
    }

    private final Node root = new Node();

    void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray())
            cur = cur.children.computeIfAbsent(c, k -> new Node());
        cur.isWord = true;
    }

    boolean search(String word) {
        Node node = find(word);
        return node != null && node.isWord;   // exact word: path AND end-flag
    }

    boolean startsWith(String prefix) {
        return find(prefix) != null;           // prefix: path is enough
    }

    // walk the path; return the node where it ends, or null if it breaks
    private Node find(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.children.get(c);
            if (cur == null) return null;
        }
        return cur;
    }
}

search and startsWith share the find walk; the only difference is whether you additionally require isWord. computeIfAbsent keeps insert clean — create the child only if missing.

Array variant

For lowercase a–z, swap the map for Node[] children = new Node[26] and index with c - 'a':

int idx = c - 'a';
if (cur.children[idx] == null) cur.children[idx] = new Node();
cur = cur.children[idx];

Complexity