Implement Trie: the idea to remember.

The core insight

Each edge consumes one character. Mark an end flag only at the final node of a stored word.

Why it works

A path exists exactly when its characters form a stored prefix. The end flag distinguishes complete words from prefixes.

The mistake to avoid

Finding a path is not enough for exact search; apple does not automatically make app a stored word.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

class Trie {
    class TNode { TNode[] children = new TNode[26]; boolean end; }
    private final TNode root = new TNode();
    void insert(String word) {
        TNode node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) node.children[i] = new TNode();
            node = node.children[i];
        }
        node.end = true;
    }
    TNode walk(String text) {
        TNode node = root;
        for (char c : text.toCharArray()) { node = node.children[c - 'a']; if (node == null) return null; }
        return node;
    }
    boolean search(String word) { TNode node = walk(word); return node != null && node.end; }
    boolean startsWith(String prefix) { return walk(prefix) != null; }
}

Make the next connection