Word Search II (LeetCode 212)
Given a character grid board and a list of words, find every word in words that can be spelled out by tracing a path through the board.
A path moves between horizontally or vertically adjacent cells one step at a time, and the same cell can't be reused twice within a single word.
Worked Examples
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]["eat","oath"]oath and eat can be traced through neighbouring cells; pea and rain cannot.board = [["a","b"],["c","d"]], words = ["abcb"][]abcb would need the b cell twice, which is not allowed.⚖️Formal Constraints & Bounds
m == board.lengthn == board[i].length1 <= m, n <= 12board[i][j]is a lowercase English letter.1 <= words.length <= 3 * 1041 <= words[i].length <= 10words[i]consists of lowercase English letters.All the strings of
wordsare unique.
Core Insight
A prefix tree converts brute-force repeated grid searches into a single branch-pruned traversal.
Real-World Scenario & Production Applications
Boggle game solvers, high-speed bioinformatic DNA motif search in genetic sequencing arrays.
Step-by-Step Execution Trace Table
| Board Cell | Visited Path | Matching Trie Prefix | Found Word |
|---|---|---|---|
| (0, 0) 'o' | ['o'] | 'o' | - |
| (0, 1) 'a' | ['o', 'a'] | 'oa' | - |
| (1, 1) 't' | ['o', 'a', 't'] | 'oat' | - |
| (2, 1) 'h' | ['o', 'a', 't', 'h'] | 'oath' | 'oath' |
| 1 | Build dictionary Trie with terminal word markers |
| 2 | def dfs(r, c, parent_node): |
| 3 | visit the cell and record a word that ends at this trie node |
| 4 | call dfs on each of the 4 neighbors whose letter is a child of this trie node |
| 5 | for r, c in grid: |
| 6 | if board[r][c] in trie: |
| 7 | dfs(r, c, root) |
Conceptual Narrative
Searching an M x N board for K words by running K separate DFS passes causes catastrophic TLE. Word Search II runs a single DFS guided by a Trie, pruning dead branches and unlinking matched words dynamically.
🧭 Conceptual Foundation & Pattern Intuition
Running naive DFS from every cell for each of the words costs , which is far too slow when and . The breakthrough is inverting the search: build a Trie from the word list, and let the board guide the Trie walk. From each grid cell , we explore adjacent cells only if the neighboring character matches a valid child in the active Trie node. If the Trie has no branch for that character, the DFS terminates immediately—pruning millions of futile paths before they start. To pass the strict LeetCode runtime constraints, two additional Senior SWE optimizations are mandatory:
- Word Deduplication: When a word is matched, clear
curr.word = Noneso the same word found via a different path is never added twice. - Dynamic Leaf Pruning: After visiting a child, if that child has zero remaining children (
len(child.children) == 0), delete it fromcurr.children. This permanently prunes exhausted branches from the Trie, preventing future DFS walks from re-exploring dead subtrees.
🗺️ The Analogy: A Scouting Party With a Single Master Compass
Imagine sending an explorer into an ancient labyrinth to search for 1,000 lost artifacts. If the explorer searches for artifact #1, then returns to the entrance and searches for artifact #2, they walk the labyrinth 1,000 separate times. Instead, you hand them a single branched blueprint (the Trie) containing all 1,000 artifact paths simultaneously. At every junction, the explorer checks the blueprint: if none of the 1,000 paths go down the left hallway, that hallway is ignored immediately. When an artifact is found, they cross it off the blueprint; if an entire branch of the blueprint is crossed off, they remove that page so no future search ever looks in that wing again.
🔑 Why It Works
Dynamic leaf pruning collapses the Trie inward as words are discovered, converting worst-case exponential backtracking into an ultra-fast directed graph reduction.
Duplicate words from different grid paths: A word can be discovered via multiple distinct DFS paths on the board. When a terminal node is reached, append
node.wordand setnode.word = Noneto prevent duplicate additions.Trie leaf node pruning omission: Failing to prune leaf nodes after all matching words in a branch are found causes unnecessary DFS traversals into dead-end branches, triggering Time Limit Exceeded.
Un-marking visited board cell on backtrack: Mutating
board[r][c] = '#'to mark visited must be revertedboard[r][c] = charupon backtrack.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Finding multiple dictionary words inside a 2D character matrix.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: grid DFS only expands into cells whose character exists as a child in the current Trie node.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Running independent DFS for each word: O(K · M · N · 4^L) vs optimal O(M · N · 4^L).
Duplicate words collected: remove
$from Trie node upon match (curr.pop('$')).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I insert all dictionary words into a Trie, storing complete words at terminal nodes. I iterate through each cell in the board and invoke DFS only if the cell character exists in the Trie root. In DFS, I mark visited cells with '#', recurse on matching neighbors, and restore the cell. Runs in O(M · N · 4^L) time and O(W · L) space."
Complexity & Mathematical Proof
O(M · N · 4^L)
Look at the execution steps: Building Trie from W words takes O(W · L). From each of the M x N grid cells, DFS explores at most 4^L paths pruned by Trie prefix matching. Total O(M · N · 4^L).
O(W · L) Auxiliary
Trie memory O(W · L) and recursion stack of max depth L.
T(M, N, L) = O(W · L) + (M · N) · 4^L
Derivation Progression
O(W · L) prefix tree build
Indexes all dictionary words simultaneously.
M · N starting positions
Initiates DFS only if character exists in root TrieNode.
4^L max steps per cell
Instantly prunes paths not matching any dictionary prefix in O(1).
Variable Definitions
Total number of rows in the grid
Total number of columns in the grid
Maximum length of any word in dictionary
Number of words in dictionary
Memory Architecture & Bounds
O(L) Recursion call stack (L = max word length)
O(W · L) Trie tree
O(K · L) List of found words
Boundary Best / Worst Cases
if no grid chars match word prefixes.
.
if all paths match valid prefixes.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "find all words on the board", "board of characters", "dictionary of words". Naive grid DFS for each dictionary word takes , which is far too slow for words. A Senior SWE inverts the search: Store Dictionary in a Trie + Single Pass Grid DFS with Prefix Pruning. If a character on the board does not match any branch in the Trie, the entire DFS subtree is pruned in !
Board , words , word length . Time budget: with aggressive Trie branch pruning, running in ms.
Duplicate words emitted: when a word can be constructed via multiple valid paths on the board, duplicate matches occur. A Senior SWE sets curr_node.word = None immediately after adding it to the result set. Trie Pruning Optimization: delete leaf nodes after finding a word (del parent.children[ch]) to prevent revisiting dead subtrees.
Word Search II (LeetCode 212)
Given a character grid board and a list of words, find every word in words that can be spelled out by tracing a path through the board.
A path moves between horizontally or vertically adjacent cells one step at a time, and the same cell can't be reused twice within a single word.
Worked Examples
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]["eat","oath"]oath and eat can be traced through neighbouring cells; pea and rain cannot.board = [["a","b"],["c","d"]], words = ["abcb"][]abcb would need the b cell twice, which is not allowed.⚖️Formal Constraints & Bounds
m == board.lengthn == board[i].length1 <= m, n <= 12board[i][j]is a lowercase English letter.1 <= words.length <= 3 * 1041 <= words[i].length <= 10words[i]consists of lowercase English letters.All the strings of
wordsare unique.
Core Insight
A prefix tree converts brute-force repeated grid searches into a single branch-pruned traversal.
Real-World Scenario & Production Applications
Boggle game solvers, high-speed bioinformatic DNA motif search in genetic sequencing arrays.
Step-by-Step Execution Trace Table
| Board Cell | Visited Path | Matching Trie Prefix | Found Word |
|---|---|---|---|
| (0, 0) 'o' | ['o'] | 'o' | - |
| (0, 1) 'a' | ['o', 'a'] | 'oa' | - |
| (1, 1) 't' | ['o', 'a', 't'] | 'oat' | - |
| (2, 1) 'h' | ['o', 'a', 't', 'h'] | 'oath' | 'oath' |
| 1 | Build dictionary Trie with terminal word markers |
| 2 | def dfs(r, c, parent_node): |
| 3 | visit the cell and record a word that ends at this trie node |
| 4 | call dfs on each of the 4 neighbors whose letter is a child of this trie node |
| 5 | for r, c in grid: |
| 6 | if board[r][c] in trie: |
| 7 | dfs(r, c, root) |
Conceptual Narrative
Searching an M x N board for K words by running K separate DFS passes causes catastrophic TLE. Word Search II runs a single DFS guided by a Trie, pruning dead branches and unlinking matched words dynamically.
🧭 Conceptual Foundation & Pattern Intuition
Running naive DFS from every cell for each of the words costs , which is far too slow when and . The breakthrough is inverting the search: build a Trie from the word list, and let the board guide the Trie walk. From each grid cell , we explore adjacent cells only if the neighboring character matches a valid child in the active Trie node. If the Trie has no branch for that character, the DFS terminates immediately—pruning millions of futile paths before they start. To pass the strict LeetCode runtime constraints, two additional Senior SWE optimizations are mandatory:
- Word Deduplication: When a word is matched, clear
curr.word = Noneso the same word found via a different path is never added twice. - Dynamic Leaf Pruning: After visiting a child, if that child has zero remaining children (
len(child.children) == 0), delete it fromcurr.children. This permanently prunes exhausted branches from the Trie, preventing future DFS walks from re-exploring dead subtrees.
🗺️ The Analogy: A Scouting Party With a Single Master Compass
Imagine sending an explorer into an ancient labyrinth to search for 1,000 lost artifacts. If the explorer searches for artifact #1, then returns to the entrance and searches for artifact #2, they walk the labyrinth 1,000 separate times. Instead, you hand them a single branched blueprint (the Trie) containing all 1,000 artifact paths simultaneously. At every junction, the explorer checks the blueprint: if none of the 1,000 paths go down the left hallway, that hallway is ignored immediately. When an artifact is found, they cross it off the blueprint; if an entire branch of the blueprint is crossed off, they remove that page so no future search ever looks in that wing again.
🔑 Why It Works
Dynamic leaf pruning collapses the Trie inward as words are discovered, converting worst-case exponential backtracking into an ultra-fast directed graph reduction.
Duplicate words from different grid paths: A word can be discovered via multiple distinct DFS paths on the board. When a terminal node is reached, append
node.wordand setnode.word = Noneto prevent duplicate additions.Trie leaf node pruning omission: Failing to prune leaf nodes after all matching words in a branch are found causes unnecessary DFS traversals into dead-end branches, triggering Time Limit Exceeded.
Un-marking visited board cell on backtrack: Mutating
board[r][c] = '#'to mark visited must be revertedboard[r][c] = charupon backtrack.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Finding multiple dictionary words inside a 2D character matrix.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: grid DFS only expands into cells whose character exists as a child in the current Trie node.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Running independent DFS for each word: O(K · M · N · 4^L) vs optimal O(M · N · 4^L).
Duplicate words collected: remove
$from Trie node upon match (curr.pop('$')).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I insert all dictionary words into a Trie, storing complete words at terminal nodes. I iterate through each cell in the board and invoke DFS only if the cell character exists in the Trie root. In DFS, I mark visited cells with '#', recurse on matching neighbors, and restore the cell. Runs in O(M · N · 4^L) time and O(W · L) space."
Complexity & Mathematical Proof
O(M · N · 4^L)
Look at the execution steps: Building Trie from W words takes O(W · L). From each of the M x N grid cells, DFS explores at most 4^L paths pruned by Trie prefix matching. Total O(M · N · 4^L).
O(W · L) Auxiliary
Trie memory O(W · L) and recursion stack of max depth L.
T(M, N, L) = O(W · L) + (M · N) · 4^L
Derivation Progression
O(W · L) prefix tree build
Indexes all dictionary words simultaneously.
M · N starting positions
Initiates DFS only if character exists in root TrieNode.
4^L max steps per cell
Instantly prunes paths not matching any dictionary prefix in O(1).
Variable Definitions
Total number of rows in the grid
Total number of columns in the grid
Maximum length of any word in dictionary
Number of words in dictionary
Memory Architecture & Bounds
O(L) Recursion call stack (L = max word length)
O(W · L) Trie tree
O(K · L) List of found words
Boundary Best / Worst Cases
if no grid chars match word prefixes.
.
if all paths match valid prefixes.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "find all words on the board", "board of characters", "dictionary of words". Naive grid DFS for each dictionary word takes , which is far too slow for words. A Senior SWE inverts the search: Store Dictionary in a Trie + Single Pass Grid DFS with Prefix Pruning. If a character on the board does not match any branch in the Trie, the entire DFS subtree is pruned in !
Board , words , word length . Time budget: with aggressive Trie branch pruning, running in ms.
Duplicate words emitted: when a word can be constructed via multiple valid paths on the board, duplicate matches occur. A Senior SWE sets curr_node.word = None immediately after adding it to the result set. Trie Pruning Optimization: delete leaf nodes after finding a word (del parent.children[ch]) to prevent revisiting dead subtrees.