Design Add and Search Words: the idea to remember.

The core insight

Insert words into a trie. During search, follow a literal edge or try every existing child for a wildcard.

Why it works

Each recursive branch consumes exactly one pattern character, so an accepted terminal path corresponds to a stored word matching every position.

The mistake to avoid

A dot matches one character, not an arbitrary length suffix. Require a terminal word marker after consuming the pattern.

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 WordDictionary {
    class TNode { TNode[] next = new TNode[26]; boolean end; }
    private final TNode root = new TNode();
    void addWord(String word) {
        TNode node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a'; if (node.next[i] == null) node.next[i] = new TNode(); node = node.next[i];
        }
        node.end = true;
    }
    boolean search(String word) { return match(root, word, 0); }
    boolean match(TNode node, String word, int i) {
        if (node == null) return false;
        if (i == word.length()) return node.end;
        char c = word.charAt(i);
        if (c != '.') return match(node.next[c - 'a'], word, i + 1);
        for (TNode child : node.next) if (child != null && match(child, word, i + 1)) return true;
        return false;
    }
}

Make the next connection