Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Store words in a trie exactly like Implement Trie. `addWord` is the standard insert. `search` is a DFS over the trie: on a normal letter follow that one child; on a `.` wildcard recurse into EVERY existing child. A match means the DFS reaches the end of the pattern at a node whose `isEnd` is true.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can extend a known structure (the trie) with a recursive search that backtracks. The dot wildcard is a deliberate fork-in-the-road that converts an iterative walk into a DFS.
Where candidates slip
Treating search iteratively and getting stuck on the dot (you can't pick one child), or returning true at the end of the pattern without checking isEnd (so a prefix wrongly matches).
How to stand out
Recognise instantly that '.' turns the walk into DFS-with-backtracking, pass node+index instead of slicing strings, short-circuit on the first matching branch, and discuss that an all-dots query can blow up to O(26^L).
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
| # | Approach | Time | Space | Jump |
|---|---|---|---|---|
| 1 | Trie + DFS Backtracking on '.' (Optimal)Optimal | addWord O(L); search O(L) with no dots, up to O(26^d · L) with d dots | O(total characters) for the trie, O(L) recursion stack | Read |
| 2 | Bucket Words by Length + Linear Scan (Naive Baseline) | addWord O(L); search O(K · L) where K = words of that length | O(total characters) | Read |
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Trie after adding "bad", "dad", "mad". search(".ad") explores all three children of root in parallel; the green b→a→d path reaches isEnd first and wins.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Trie + DFS Backtracking on '.' (Optimal)
1Hint 1Explore hintHide hint
Store the words in a normal trie — addWord is just insert.
2Hint 2Explore hintHide hint
search a word without dots is a plain trie walk. Now: what do you do at a '.', where any letter is acceptable?
3Hint 3Explore hintHide hint
At a '.', you can't pick one child, so try them ALL — recurse into each child for the rest of the pattern and succeed if any branch matches.
A · Core idea
Reuse the Implement-Trie skeleton: nodes have a children map and an isEnd flag, and addWord is the unchanged insert. All the new work lives in search.
Why search must become recursive. Without wildcards, search is the same iterative walk as Implement Trie — follow one child per character, check isEnd at the end. The moment a . appears, the iterative walk breaks: you can no longer pick the child, because any of the (up to 26) children is a legal match. The natural way to 'try all options and accept if one works' is depth-first search with backtracking.
Why a dot branches over every child. A . means 'any single character'. So from the current node, each existing child is a candidate for that position. We recurse into every child with the rest of the pattern (index + 1) and return true if any of those sub-searches succeeds — that's the any(dfs(child, i+1) ...) line. A literal letter is the degenerate case: exactly one child is a candidate, so we recurse into just that one (or fail if it's missing).
Why the base case checks isEnd, not just true. When the pattern index reaches the word length, we've consumed the whole pattern. But matching the characters isn't enough — a stored word must actually end at this node. Returning node.isEnd (not true) is what stops "ba" from matching when only "bad" was inserted. This is the same isEnd discipline as Implement Trie, now inside a recursion.
Why we pass node + index. Carrying the current node and the position in the pattern (rather than slicing the string at each step) keeps each call O(1) extra work and avoids quadratic string copying. It also makes backtracking automatic: when a branch returns false, the recursion unwinds and the caller simply tries the next child.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
added {"bad","dad","mad"}; search(".ad")Interactive diagram
Search recursion as a decision tree
dfs(root, 0)A literal character takes the single-child edge; a dot fans out to all children and backtracks until one branch reaches an isEnd node.
trueC · Code with teaching comments
D · Why it works and complexityaddWord O(L); search O(L) with no dots, up to O(26^d · L) with d dots timeO(total characters) for the trie, O(L) recursion stack spaceOpen the invariant and proofExplore the proofHide the proof
The literal-vs-dot distinction is the whole algorithm: a letter PRUNES the search to one child, a dot EXPANDS it to all children. Search cost is therefore driven entirely by how many dots the query has — pure-letter queries stay O(L), dotty queries fan out. This 'walk the trie, but branch and backtrack at choice points' move is exactly what Word Search II does on a grid.
ComplexityaddWord O(L); search O(L) with no dots, up to O(26^d · L) with d dots time, O(total characters) for the trie, O(L) recursion stack space — addWord walks L characters, O(1) each → O(L). search follows one child per literal character; each '.' multiplies the branching by the number of children (≤26). With d dots the worst case is O(26^d · L), but with no dots it stays O(L). The trie stores the sum of all inserted characters; recursion depth is at most L.
E · Edge cases and pitfalls5search(".ad") after adding only "bad" — Dot branches over root's children; only 'b' exists, b→a→d ends on isEnd → true. Confirms the dot tries existing children, not all 26 blindly.Explore edge casesHide edge cases
Edge cases handled
search(".ad") after adding only "bad"Dot branches over root's children; only 'b' exists, b→a→d ends on isEnd → true. Confirms the dot tries existing children, not all 26 blindly.search("b..") after adding "bad"Follow 'b', then two dots each branch over the single available child a→d, landing on isEnd → true.
Pitfalls
- Returning true (not node.isEnd) at the base case — lets a prefix like "ba" match when only "bad" was added.
- On a dot, iterating all 26 array slots without the null check — you'd recurse into non-existent children and crash or waste work.
- Slicing the word (word[1:]) on each recursion instead of passing an index — turns each call into O(L) string work, quadratic overall.
Approach 2 of 2
Bucket Words by Length + Linear Scan (Naive Baseline)
1Hint 1Explore hintHide hint
A '.' matches any single character, so a candidate word must have the SAME length as the pattern.
2Hint 2Explore hintHide hint
Group stored words by length in a hash map: length → list of words.
3Hint 3Explore hintHide hint
search compares the pattern against every same-length word position-by-position, treating '.' as a wildcard. Simple, but it scans the whole bucket.
A · Core idea
Since . matches exactly one character, any matching word has the same length as the pattern. So bucket the words by length, and on search compare the pattern against each same-length word, treating . as 'always equal'.
Why it's a reasonable first thought. It directly exploits the same-length observation and needs no tree. For small dictionaries it's perfectly fast and trivially correct.
Why it doesn't scale. All the words of a given length sit in one bucket with no shared structure, so search must scan the entire bucket — O(K · L). With up to 10⁴ words, many sharing a length, repeated searches become a per-call linear scan. There's no prefix sharing and no early pruning: even a query that diverges on the first character still pays to start comparing every word.
Why the trie wins. The trie shares prefixes, so a literal character immediately prunes to one branch and a search that diverges early stops early. The bucket scan has no such pruning. Mention this baseline to show the same-length insight, then upgrade to the trie + DFS.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
added {"bad","dad","mad"}; search(".ad")bucket lookup
len(".ad") = 3 → bucket ["bad","dad","mad"]
K = 3 candidatestrueC · Code with teaching comments
Reference implementation previewclass WordDictionary { private final Map<Integer, List<String>> byLen = new HashMap<>(); public WordDictionary() {} Explore the full codeHide the full code
D · Why it works and complexityaddWord O(L); search O(K · L) where K = words of that length timeO(total characters) spaceOpen the invariant and proofExplore the proofHide the proof
Bucketing by length captures the 'dot matches one char' insight but throws away prefix structure, so it can never prune — every search rescans a whole bucket. The trie keeps the prefix structure, turning the scan into a guided DFS that abandons dead branches immediately.
ComplexityaddWord O(L); search O(K · L) where K = words of that length time, O(total characters) space — addWord appends to a list in O(L). search examines every word in the matching-length bucket and compares L characters each → O(K · L), where K can be large when many words share a length.
E · Edge cases and pitfalls4search("xyz") with no length-3 words — Bucket lookup returns null/empty → false immediately. The one case where it's genuinely fast.Explore edge casesHide edge cases
Edge cases handled
search("xyz") with no length-3 wordsBucket lookup returns null/empty → false immediately. The one case where it's genuinely fast.
Pitfalls
- Comparing words of different lengths — a '.' matches exactly one char, so only same-length words can match.
- Forgetting the bucket may be absent (null) and dereferencing it.
- Assuming this is 'good enough' — with many same-length words it becomes a per-query linear scan the trie avoids.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewclass WordDictionary { private static class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEnd = false; }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Base case returns true instead of isEnd
When the pattern is consumed, the path's characters all matched — but a stored WORD must actually end at this node. Returning true lets a strict prefix match: search("ba") would return true after only "bad" was added.
Explore the code comparisonHide the code comparison
Base case returns true instead of isEnd
When the pattern is consumed, the path's characters all matched — but a stored WORD must actually end at this node. Returning true lets a strict prefix match: search("ba") would return true after only "bad" was added.
Don't write this
def dfs(idx, node):
if idx == len(word):
return True # WRONG — ignores whether a word ends here
...Write this instead
def dfs(idx, node):
if idx == len(word):
return node.is_end # must terminate on a real word
...2Branching into non-existent children on a dot
Iterating a fixed 26-slot array and recursing without the null check explores edges that don't exist — at best wasted work, at worst a NullPointerException one level down.
Explore the code comparisonHide the code comparison
Branching into non-existent children on a dot
Iterating a fixed 26-slot array and recursing without the null check explores edges that don't exist — at best wasted work, at worst a NullPointerException one level down.
Don't write this
for (TrieNode child : node.children) {
if (dfs(word, idx + 1, child)) return true; // child may be null
}Write this instead
for (TrieNode child : node.children) {
if (child != null && dfs(word, idx + 1, child)) return true;
}3Slicing the pattern each recursion
Calling dfs(word[1:], node) copies the suffix on every level, turning an O(L) search into O(L²) and allocating garbage. Pass an index instead.
Explore the code comparisonHide the code comparison
Slicing the pattern each recursion
Calling dfs(word[1:], node) copies the suffix on every level, turning an O(L) search into O(L²) and allocating garbage. Pass an index instead.
Don't write this
def dfs(word, node):
if not word:
return node.is_end
return dfs(word[1:], child) # O(L) copy per callWrite this instead
def dfs(idx, node):
if idx == len(word):
return node.is_end
return dfs(idx + 1, child) # O(1) per callRevise
Carry the pattern into the interview
Pattern to remember
Trie + DFS backtracking to handle '.' wildcards
Code pattern to memorize
def dfs(node, i):
if i == len(word): return node.isEnd
ch = word[i]
if ch == '.':
return any(dfs(child, i+1) for child in node.children.values())
return ch in node.children and dfs(node.children[ch], i+1)Rules to remember
- 1A
.matches any single character → recurse into every child of the current node. - 2A normal letter follows exactly one child; bail out (return false) if that child is missing.
- 3The base case (pattern exhausted) returns node.isEnd, not just true — the path must end on a real word.
- 4Pass the node + index down the recursion; don't slice the string repeatedly.
- 5Return as soon as any branch matches (
any(...)) — don't keep searching once one path succeeds.
Use this pattern when
- Exact-match dictionary plus single-character wildcards in queries
- Pattern matching where '.' (or '?') stands for 'any one character'
- You already reach for a trie, and queries are partly unknown
- Regex-lite matching over a fixed word set
Choose another pattern when
- No wildcards → a plain HashSet / Trie search is enough
- Wildcards can match MANY characters ('*') → this is full regex / DP, not a single-step branch
- Only one word ever stored → DFS over a trie is overkill
- Patterns are mostly dots → DFS fans out to O(26^L); consider constraints carefully
Interview takeaway
The wildcard is the whole problem: a literal letter prunes to one child, a dot forces you to branch over all children and backtrack. It's the canonical 'trie + DFS' marriage — once you can write this search, Word Search II's grid DFS over a trie feels like the same move.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Trie + DFS backtracking. Recognise it when an exact-match dictionary gains single-character wildcards: literals prune to one child, dots fan out to all. The same 'walk a trie but branch at choice points' shape powers Word Search II.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Implement Trie (Prefix Tree)The base structure here — drop the wildcard and search becomes a plain iterative walk.
- Word Search IISame trie + DFS idea, but the DFS runs over a 2D grid and prunes by the trie.
- Regular Expression MatchingComing soonAdds '*' (zero-or-more), which breaks the same-length invariant and needs DP, not a single-step branch.
- Wildcard MatchingComing soon'?' is this problem's '.', but '*' matches any sequence — again DP territory.