Pattern this teaches:Trie
Word Search II
A hard Backtracking interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Backtracking
- Sheets
- 2
- Core for
- 0 roles
The problem
A grid of letters and a list of words are given. A word is found when you can spell it by moving between cells that touch up, down, left or right, without stepping on any cell twice for that word. Return every word from the list that can be found.
Example 1
- Input
- board = [["c","r","a","b"],["t","o","n","e"],["s","e","a","m"]], words = ["crab","tone","cone","rot"]
- Output
- ["crab","rot","tone"]
- Why
- crab runs along the top row, tone along the middle row, and rot bends from r down to o and t. cone would need a diagonal step, so it is not found.
Example 2
- Input
- board = [["p","q"],["r","s"]], words = ["pqsp"]
- Output
- []
- Why
- The path would have to reuse the p cell, which is not allowed.
Constraints
- m == board.length
- n == board[i].length
- 1 <= m, n <= 12
- board[i][j] is a lowercase English letter
- 1 <= words.length <= 3 * 10^4
- 1 <= words[i].length <= 10
- words[i] consists of lowercase English letters
How to think about it
Updated 2026-09-29Searching the board separately for each word duplicates traversal of shared prefixes across thousands of words. Inverting the perspective by indexing all words into a prefix Trie allows a single board DFS to advance through the Trie simultaneously, abandoning entire families of words the moment the board's path diverges from the Trie.
Approaches, worst first
Individual word DFS search
time O(W * m * n * 4^L) · space O(L)
For each word in words, scan the board for starting characters and run DFS backtracking. Re-explores identical paths on the board for words sharing prefixes like 'apple', 'application', and 'apply', leading to severe time limit violations with 30,000 words.
Trie-directed board traversal
time O(m * n * 4^L) · space O(TotalCharacters)
Build a Trie of all words. From each board cell, step into the Trie matching board[r][c]. Backtrack in 4 directions, advancing both grid position and Trie node. When a node marks word completion, collect the word and nullify its marker to prevent duplicates.
Trie traversal with leaf pruningWrite this one
time O(m * n * 4^L) · space O(TotalCharacters)
Enhance Trie DFS by pruning leaf nodes after words are found. Once a leaf node's word is recorded, remove that branch from the parent. This ensures subsequent board paths do not waste time traversing dead branches for already-found words.
Where people lose marks · 3
- Adding duplicate entries of the same word when multiple distinct paths on the board form the same word. Clearing node.word to null after recording it guarantees uniqueness.
- Failing to restore board[r][c] from its visited sentinel (such as '#') when backtracking, corrupting the board for neighboring starting cells.
- Retaining exhausted leaves in the Trie, causing later cell traversals to repeat exploration for words that have already been discovered.
The theory behind it
Backtracking — the ground this problem stands on. All Backtracking problems
What Backtracking is
Backtracking is an organized trial-and-error search through a maze of possibilities. You make a tentative choice, move forward to explore where that path leads, and if you hit a dead end or finish finding an answer, you back up and undo that choice. By cleaning up your changes before trying the next option, a single shared board or list is explored thoroughly without needing to clone full copies of your data at every turn.
When to reach for it
Reach for backtracking when a problem asks to generate all possible solutions, like all subsets, permutations, valid parentheses combinations, or word search paths on a board. Signals include puzzles with strict constraint rules, like placing eight non-attacking queens on a chessboard or solving a Sudoku grid. Whenever you must construct combinations step by step and abandon dead-end branches early before wasting time exploring impossible paths, use backtracking.
How the pattern works
Follow a three-step rhythm inside a loop: choose, explore, and unchoose. First, check if the current state satisfies your goal; if so, save a copy of it and return. Next, prune illegal moves immediately using constraint checks so unpromising branches are skipped. For each valid candidate, apply the move to your shared path or board, call the recursive function to explore deeper, and finally undo the move right after the call returns. Undoing restores the shared state so sibling choices start from a clean slate.
More Backtracking problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .