A crossword-lexicon API stores lowercase answers. The fill-aid asks whether any stored word matches a pattern: known letters stay, blanks arrive as .. Staging kept every answer in an ArrayList and scanned with a per-character match. A few hundred clues returned in milliseconds. The live lexicon made every keystroke a full pass, and the fill-aid timed out.

Add words, then search with . matching any letter. A trie already gives the layout: children plus an end mark, Node[26] when the alphabet is a–z. Implement Trie is exact search — one child per letter, then the end mark. DFS owns recursion versus an explicit stack. Here addWord is that insert. search is that walk until a ., then DFS fans out over the live children from that node. Do not stamp finish times. Do not compile a Pattern.

The problem

Build a class that stores lowercase words: addWord(word) inserts, and search(word) is true if some inserted word matches — a letter must sit on that edge, . matches any single letter. Keep those two names.

addWord("ship")
addWord("shop")
addWord("sharp")
search("ship")     →  true
search("shi")      →  false
search("shi.")     →  true
search("sh.p")     →  true
search("s....")    →  true
search(".harp")    →  true
search("shot")     →  false

Note: ca is a prefix of cat, not a word — same end-mark trap as Implement Trie. search("shi") walks to i and finds the mark off. . matches one letter, not a gap of any length.

A list of whole words is the honest brute force

Store every added string in a list. search scans for the same length, then per character a . matches anything and a letter must equal — correct, linear in the catalog per query.

class WordDictionaryScan {
    final List<String> words = new ArrayList<>();

    void addWord(String word) {
        words.add(word);
    }

    boolean search(String word) {
        for (String stored : words) {
            if (matches(stored, word)) {
                return true;
            }
        }
        return false;
    }

    boolean matches(String stored, String pattern) {
        if (stored.length() != pattern.length()) {
            return false;
        }
        for (int i = 0; i < stored.length(); i++) {
            char p = pattern.charAt(i);
            if (p != '.' && p != stored.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

A HashSet would make exact search a lookup, the Implement Trie brute. One . throws you back to a scan of n. String.matches is that same scan dressed as a regex — compiling a Pattern per query is not the intended structure. At a few hundred clues this is a rounding error. At a live lexicon you paid n for a question a character walk answers by following edges: does this path exist, and did a word end here?

Same insert; DFS every child when the query is .

Reuse the same inner Node: Node[] children = new Node[26] and boolean endOfWord. addWord is that iterative insert. search follows a letter down one child and DFS over live children when the character is . — at the end of the query the end mark must be true.

addWord("ship")
  create s → h → i → p    mark p

addWord("shop")
  reuse s → h             create o → p, mark p

addWord("sharp")
  reuse s → h             create a → r → p, mark p

search("shi.")
  s, h, i exact; `.` tries children of i → p, end mark on → true

search("sh.p")
  s, h exact; `.` tries i, o, a
    i → p, end mark on → true

search("s....")
  s, then four dots: "ship" / "shop" die at length 4; "sharp" matches

search("shi")
  walk to i; end mark off → false

The Java is that class. Recursion is for the fan-out, not for addWord.

class WordDictionary {
    static final class Node {
        final Node[] children = new Node[26];
        boolean endOfWord;
    }

    final Node root = new Node();

    void addWord(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Node();
            }
            node = node.children[idx];
        }
        node.endOfWord = true;
    }

    boolean search(String word) {
        return dfs(word, 0, root);
    }

    boolean dfs(String word, int i, Node node) {
        if (node == null) {
            return false;
        }
        if (i == word.length()) {
            return node.endOfWord;
        }
        char c = word.charAt(i);
        if (c == '.') {
            for (Node child : node.children) {
                if (child != null && dfs(word, i + 1, child)) {
                    return true;
                }
            }
            return false;
        }
        return dfs(word, i + 1, node.children[c - 'a']);
    }
}

Time for addWord is O(L) — one step per character, same insert as Implement Trie. Search with no dots is O(L) — one child per letter. Search of L dots is O(26^L) in the worst case — a 26-way branch at every position. Space is the nodes you allocated. Do not re-lecture prefix sharing or the DFS walk at the board unless they ask; those posts already own both.

Note: Adding a word that is already present only sets the end mark again. It does not allocate a second path.

What interviewers usually poke next

  • No-dot fast path. If the query has no ., the iterative walk from Implement Trie is enough — you do not need 26-way recursion. Say that as an optimization; the one recursive search is still correct.
  • Unicode, mixed case, punctuation. Node[26] is for a–z. A Map of children is the honest default for a wider alphabet — the trie post owns that choice; do not paste a second class here.
  • . is not *. This prompt matches exactly one letter. A Kleene star, optional letters, or String.matches is a different automaton. Do not compile a regex.
  • Word Search II. DFS on trie children, next character from a neighbor cell on a board. Same fan-out, different source for the next letter.
  • Search Suggestions. Walk an exact prefix, then rank words in that subtree. Suggestions do not branch on .; this prompt does not collect or rank a subtree.

You are done with this problem when you can say, out loud, why the list scan is correct, why a . is DFS over children and not a regex, and why search still reads the end mark.