Design Add and Search Words Data Structure

1. Problem & Core Objective

Support adding words and searching with a wildcard:

void    addWord(String word)
boolean search(String word)    // '.' matches ANY single character

addWord("bad"); addWord("dad"); addWord("mad");
search("pad")  → false
search("bad")  → true
search(".ad")  → true      ← '.' matches b, d or m
search("b..")  → true      ← both dots match anything

Constraints: 1 <= word.length <= 25 · lowercase letters and . · at most 2 dots in any search · up to 10^4 calls

What's actually being tested: extending the trie walk into a search with backtracking. A concrete character follows exactly one edge; a . must try every child. That turns an iterative walk into a DFS — and the "at most 2 dots" constraint is what keeps the branching survivable.

2. First-Principles Thought Process

Start from what changes

Question 1's search was a straight walk: at each character, follow that one edge or fail. There was never a choice to make, so no backtracking was needed.

A . breaks that. It matches any character, so at that position the search must consider every existing child and succeed if any of them leads to a match.

One choice point makes it a DFS

The moment a step has multiple options and you need "does any option work?", you have a search tree, and recursion is the natural expression:

dfs(word, i, node):
    if i == word.length:  return node.isEnd
    c = word[i]
    if c == '.':
        for each non-null child: if dfs(word, i+1, child) return true
        return false
    else:
        child = node.children[c - 'a']
        return child != null && dfs(word, i+1, child)

The concrete-character branch is the old iterative walk. Only the . branch is new.

Why it doesn't explode

Each . multiplies the search by up to 26. With d dots that's O(26^d · L).

The constraint caps d at 2, so the worst case is 26² = 676 paths of at most 25 steps — about 17,000 operations per search, and 10^4 searches gives 1.7 × 10^8 worst case. Tight but workable.

And the real branching is far smaller than 26, because you only iterate children that actually exist. A trie built from three words has at most 3 children at the root, not 26. The 26^d bound assumes a dense trie that real dictionaries never produce.

Where the pruning comes from

A . at a node with two children tries two paths, not 26. That's the trie's negative answer doing work again: absent children cost nothing.

3. Solution Paths

Approach 1 — Store words, match each with a regex or manual scan (brute force)

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

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

    public boolean search(String word) {
        for (String w : words) {
            if (w.length() != word.length()) continue;         // cheap reject
            boolean ok = true;
            for (int i = 0; i < w.length(); i++)
                if (word.charAt(i) != '.' && word.charAt(i) != w.charAt(i)) { ok = false; break; }
            if (ok) return true;
        }
        return false;
    }
}

• Time addWord O(1), search O(n · L) · Space O(n · L)

Counter-questions on this approach

⭐ "This is simple and the length check prunes a lot. Why isn't it enough?"

It scales with the dictionary, not the word. With 10^4 calls against a dictionary that grows to 10^4 words of 25 characters, search is O(n · L) = 2.5 × 10^5 per call, so 2.5 × 10^9 overall. Too slow.

The trie's cost depends on the query length and the dot count, not on how many words are stored. That independence is the whole point.

⭐ "What does the length check actually buy?"

A lot in practice — it rejects most candidates in O(1), since a wildcard pattern matches only words of exactly its length. That makes this solution much faster than its bound suggests on realistic input.

But it's still linear in n, and worse, it's an optimisation the trie gets structurally: words of the wrong length diverge from the search path naturally, without a special check.

"Would a regex be better?"

Pattern.compile(word.replace(".", ".")) — the pattern is already valid regex, since . means the same thing. But you'd compile per search, or cache compiled patterns, and you'd still test every word. It's the same O(n · L) with a worse constant. Java's regex engine is also backtracking, so no asymptotic help.

"Any structure that would fix this without a trie?"

Bucket words by length, which cuts n to the words of matching length. Or index by (position, character) and intersect sets for the non-dot positions. Both help, neither reaches O(L), and both are more machinery than a trie.

Approach 2 — Trie with DFS on wildcards (optimal)

class WordDictionary {
    private static class Node {
        Node[] children = new Node[26];
        boolean isEnd;
    }

    private final Node root = new Node();

    public void addWord(String word) {
        Node node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) node.children[i] = new Node();
            node = node.children[i];
        }
        node.isEnd = true;
    }

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

    private boolean dfs(String word, int i, Node node) {
        if (i == word.length()) return node.isEnd;      // consumed the pattern

        char c = word.charAt(i);
        if (c == '.') {
            for (Node child : node.children)             // try every EXISTING child
                if (child != null && dfs(word, i + 1, child)) return true;
            return false;
        }

        Node child = node.children[c - 'a'];
        return child != null && dfs(word, i + 1, child);
    }
}

Trace — dictionary {bad, dad, mad}, searching ".ad":

Only the first branch was explored — the d and m subtrees were never touched.

Trace — searching ".at" (no match):

Three branches, each dying at depth 2 — never reaching depth 3.

• Time addWord O(L), search O(L) with no dots, O(26^d · L) worst case · Space O(N × 26) references

Counter-questions on this approach

⭐ "Why does search need recursion when question 1's didn't?"

Because a . creates a choice point. With concrete characters there's exactly one edge to follow at each step, so a loop suffices — no state to remember, nothing to undo.

A . needs "try this child; if it fails, try the next". That's backtracking, and recursion gives me the position save-and-restore for free via the call stack. I could do it iteratively with an explicit stack of (index, node) pairs, but the recursion mirrors the structure exactly.

⭐ "What's the real cost of a dot? Is 26^d honest?"

It's the worst case, and it's pessimistic. The loop iterates the 26-slot array but only recurses into non-null children, so the real branching is the node's actual number of children.

For a dictionary of three words the root has 3 children, not 26. A dot near the root of a large dictionary could genuinely branch 26 ways, but dots deeper in are far cheaper because the trie narrows. I'd quote O(26^d · L) as the bound and say the practical cost is much lower.

The constraint caps d at 2, so even the worst case is 676 × 25 ≈ 17,000 operations.

⭐ "Why is the base case return node.isEnd rather than return true?"

Same reason as question 1. Reaching a node means the pattern matched a path, but a path is a prefix, not necessarily a word. search("ba") against a dictionary of {bad} walks successfully to the a node and must return false.

The wildcard doesn't change that — search("b.") should also be false for the same reason.

"Why for (Node child : node.children) rather than indexing 0..25?"

Identical behaviour; the enhanced-for reads better. Either way I iterate 26 slots and skip nulls. If I wanted to avoid touching empty slots I'd use a HashMap per node and iterate values(), which visits only real children — worth it for a sparse trie.

"Could a dot ever match the end of a word — search("bad.") on {bad}?"

No, and the code handles it correctly. At i = 3 the node is bad, and the dot loop finds no children, returning false. A . must match an actual character; it can't match nothing. Worth checking rather than assuming, since "matches any character" is sometimes misread as "matches anything including empty".

"What if the search string were all dots?"

search("...") asks "is there any 3-letter word?". With d = L the bound is 26^L, which is why the 2-dot constraint exists. Without it you'd need a different structure — bucketing by length would answer the all-dots case in O(1).

Comparison

4. Why the Optimal Wins

The list scan's cost is tied to how many words you've stored. The trie's is tied to how long the query is and how many wildcards it has. With 10^4 words that's the difference between 2.5 × 10^5 and 25 operations for a dot-free search.

The wildcard case is where the trie's structure pays off a second time: a . branches only over children that exist, so absent letters cost nothing. The list has no equivalent — it must examine every word regardless.

The framing worth keeping:

A concrete character follows one edge; a wildcard branches over all existing children. That single difference turns a walk into a DFS — and the trie keeps the branching factor down to what's actually there.

5. Java Prerequisites

DFS over a trie with an index

private boolean dfs(String word, int i, Node node) {
    if (i == word.length()) return node.isEnd;   // base: pattern consumed
    ...
}

Passing the index rather than substringing avoids O(L) copies at every level — word.substring(1) inside a recursion turns O(L) into O(L²).

Short-circuit on the first success

for (Node child : node.children)
    if (child != null && dfs(word, i + 1, child)) return true;
return false;

&& also guards the null before recursing.

Iterating a fixed array vs a map

for (Node child : node.children) { ... }   // visits 26 slots, skips nulls
for (Node child : map.values())  { ... }   // visits only real children

Recursion depth is bounded by the word length — at most 25 here, so no stack concern.

6. Interview Communication Guide

Clarifying questions: Does . match exactly one character, or one-or-more (exactly one — it matters)? How many dots can appear (at most 2; this bounds the branching)? Can the pattern be all dots (then it's "any word of this length")? Lowercase only (yes)?

The pitch

"Adding a word is the standard trie insert. The interesting part is search.

Without wildcards it's a straight walk — each character follows exactly one edge, so a loop is enough and there's never a choice to undo.

A . changes that, because it matches any character. At that position I have to try every existing child and succeed if any of them works. That's a choice point, which means backtracking — so I write search as a DFS carrying the current pattern index and trie node.

The concrete-character case is unchanged: follow the one edge or fail. Only the dot branches.

The base case is i == word.length(), and it returns node.isEnd, not true — same as the previous question. Matching a path only proves the pattern is a prefix; isEnd is what makes it a word.

Cost: O(L) with no dots, and each dot multiplies by the branching factor — so O(26^d · L) in the worst case. The constraint caps dots at 2, giving about 676 paths of 25 steps.

But that bound is pessimistic, because I only recurse into children that exist. A dictionary of three words gives the root three children, not 26. The trie prunes the branching down to what's actually stored, which is exactly what a list of words can't do."

Edge cases to volunteer:

Name the first two. search("b.") returning false is what the isEnd base case protects; search("bad.") returning false is what stops a dot being read as "or nothing". Both pass silently in a broken implementation that returns true on reaching any node.

7. Follow-Up Questions — Modified Constraints

⭐ "What if * matched zero or more characters?"

Much harder. * doesn't consume a fixed amount, so at each position you must try "match nothing here" and "match one more and stay on the *". That's the classic regex/wildcard DP — O(L_pattern × L_word) per word if you match against words directly, and on a trie it becomes a DFS where the * state can revisit the same node at different depths. Worth saying plainly that it's a different algorithm, not a tweak.

⭐ "What if the number of dots were unbounded?"

26^d becomes unusable — search("....................") would be hopeless. The fix is to exploit the fixed length: bucket the trie by word length, or index words by (position, character) and intersect the sets for the non-dot positions, using the length bucket as the base set. An all-dots query then becomes "is this length bucket non-empty?", answered in O(1).

"Return all matching words, not just whether one exists."

Drop the early return and collect every path that reaches an isEnd node, building the word as you descend. The cost becomes O(26^d · L + output), and you lose the short-circuit — so the typical case gets slower even though the bound is the same.

"Support a character class like [abc] instead of .."

A small generalisation: instead of iterating all children, iterate only the children named in the class. That's strictly cheaper than ., and it's a nice illustration that . is just the widest possible class.

"What if words could be deleted?"

Clear isEnd, then prune nodes with no children and no isEnd on the way back up — same as the previous question. The wildcard search is unaffected, but pruning genuinely helps here: removing dead branches directly reduces the dot branching factor.

"Make it thread-safe with concurrent reads and writes."

Reads are safe among themselves; a concurrent addWord can make a reader observe a half-linked node. A ReadWriteLock is the simple answer. Better for a read-heavy workload: make nodes immutable and publish new subtrees with a volatile write, so readers either see the old trie or the new one. Worth noting that the 26-array makes copy-on-write expensive.