Word Search Problem: How Would You Solve It?
Learn how to solve the word search grid problem with backtracking DFS, including complexity and trie-based optimizations.
Expected Interview Answer
Word search is solved with backtracking DFS: from every cell matching the word's first letter, recursively explore the four orthogonal neighbors while the next character matches, temporarily marking the current cell visited so the search never reuses a cell within the same path, then unmarking it on backtrack so other starting paths can still use it.
The algorithm scans every cell of the grid as a candidate starting point, and for each candidate it launches a depth-first search matching one character of the target word per recursive call. Marking the current cell as visited before recursing and restoring it afterward is the classic backtracking pattern, since without unmarking, cells consumed on a failed path would incorrectly stay blocked for other unrelated paths. The recursion terminates successfully once the full word length has been matched, and it prunes immediately whenever a neighbor's character does not match the next required letter or the neighbor is out of bounds or already in use on the current path. Worst-case time is O(rows * cols * 4^L) where L is the word length, since each of the four directions is tried at every step, though pruning on mismatches keeps real-world performance far below that bound.
- Explores only viable paths via early pruning on character mismatch
- O(1) extra space per cell using in-place visited marking
- Generalizes to multi-word search using a trie for shared-prefix pruning
- Simple four-directional adjacency keeps the recursion tractable
AI Mentor Explanation
A word search grid is like a fielding position chart where a scout needs to trace a chain of fielders whose surname initials spell a target sequence, moving only to adjacent fielding positions on the field diagram. The scout tries starting from every fielder whose initial matches the first letter needed, then steps to a neighboring position only if its initial matches the next required letter. While tracing a path the scout temporarily benches the current fielder so the same fielder is not reused twice within one chain, then un-benches them the moment that chain fails so they remain available for a different starting attempt. This mark-and-unmark discipline is exactly what lets the scout explore every possible chain without permanently losing access to any fielder.
Step-by-Step Explanation
Step 1
Scan for a matching start cell
Iterate every grid cell; when its character matches the word’s first letter, launch a DFS from there.
Step 2
Mark and recurse
Temporarily mark the current cell visited, then recurse into up to four orthogonal neighbors for the next character.
Step 3
Prune on mismatch
Stop immediately if the neighbor is out of bounds, already visited on this path, or does not match the required next letter.
Step 4
Unmark on backtrack
Restore the cell before returning so other starting points can still use it; return true once the full word length is matched.
What Interviewer Expects
- Identify this as backtracking DFS, not plain DFS or BFS
- Explain why the visited marking must be undone on backtrack
- State the worst-case time complexity O(rows * cols * 4^L)
- Mention trie-based pruning as an optimization for searching many words at once
Common Mistakes
- Forgetting to unmark a cell after a failed path, permanently blocking it for other attempts
- Allowing diagonal moves when the problem specifies only orthogonal adjacency
- Not pruning early on a character mismatch, wasting recursive calls
- Using a separate visited set instead of in-place marking, adding unnecessary space
Best Answer (HR Friendly)
“I approach this with backtracking DFS: I try every cell that matches the first letter as a starting point, then walk to neighboring cells only while letters keep matching, temporarily marking cells used so I don't reuse them in the same path. If a path fails, I undo that marking so the cell is still available for a different attempt.”
Code Example
def exist(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word):
return True
if r < 0 or r >= rows or c < 0 or c >= cols:
return False
if board[r][c] != word[i]:
return False
temp, board[r][c] = board[r][c], "#"
found = (
dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or
dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1)
)
board[r][c] = temp
return found
for row in range(rows):
for col in range(cols):
if dfs(row, col, 0):
return True
return FalseFollow-up Questions
- How would you search for multiple words efficiently using a trie?
- What is the space complexity of this recursive solution?
- How would you handle a grid with diagonal adjacency allowed?
- How would you count all distinct paths that spell the word instead of stopping at the first?
MCQ Practice
1. Why must a visited cell be unmarked after a failed recursive path?
Backtracking requires restoring state so a cell blocked on one failed path remains usable for unrelated paths.
2. What is the worst-case time complexity of the word search backtracking solution?
Each of the up to L characters can branch into up to 4 directions, giving O(rows * cols * 4^L) in the worst case.
3. What data structure optimizes searching for many words in the same grid?
A trie lets the DFS share and prune common prefixes across multiple target words simultaneously.
Flash Cards
What algorithmic technique solves word search? — Backtracking DFS with in-place visited marking and unmarking.
Why unmark a cell after backtracking? — So it remains available for other paths that did not use it on a failed attempt.
What is the worst-case time complexity? — O(rows * cols * 4^L), where L is the word length.
How do you optimize for searching multiple words? — Build a trie from all target words so the DFS can prune shared prefixes.