Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Determine whether `word` can be spelled by a path of adjacent cells in the grid (no cell reused). The canonical answer is DFS + backtracking from every cell: match a letter, mark the cell visited, recurse into the 4 neighbours, then UN-mark on the way out. The in-place '#' marking trick avoids a separate visited matrix; restoring the cell after the recursion is the backtracking discipline that lets other paths reuse it.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can write a clean recursive grid DFS with correct backtracking — marking a cell visited on entry and restoring it on exit — and whether you launch the search from every valid starting cell.
Where candidates slip
Forgetting to restore the cell after the recursion (so a letter consumed on one branch stays blocked for others), or using a path that revisits the same cell because there's no visited-marking at all.
How to stand out
Use the in-place '#' marking trick to avoid an O(mn) visited matrix, prune starts where the first letter doesn't match, and mention the frequency / reverse-word optimisations and the Trie generalisation (Word Search II).
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Each node is a (cell, letter-index) state. We choose a cell, mark it '#', explore 4 neighbours, then restore it. The path that completes the word is highlighted; branches that hit a mismatch or a visited cell are pruned.
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
Brute Force — Enumerate All Paths Without Pruning
1Hint 1Explore hintHide hint
The literal idea: from each starting cell, walk out in all 4 directions building a string, and compare the full L-length string to `word` at the end.
2Hint 2Explore hintHide hint
To honour no-reuse you carry a visited set; without pruning you keep walking even after the prefix already disagrees with `word`.
3Hint 3Explore hintHide hint
This explores enormous numbers of length-L paths that diverged from `word` at the very first letter — checking the match only at the end is the waste.
A · Core idea
The most literal approach: from every cell, generate every length-L walk over adjacent, non-reused cells, materialise the string it spells, and compare to word at the end.
Why it's a reasonable first framing. It correctly captures the search space — paths through the grid — and the no-reuse constraint via a visited set. Saying it out loud shows you understand the shape of the problem before optimising.
Why it's wasteful. It checks the letter match only after building a full path, so it explores every one of the ~4^L walks even when the prefix disagrees with word at letter 0. A path starting on a cell that doesn't even equal word[0] is pursued to full depth. Carrying a separate visited matrix that you allocate per start (instead of marking in place) adds constant-factor overhead and memory churn.
The fix it points to. Fuse the match-check into the walk: validate board[r][c] == word[k] at the top of each recursive step and bail the instant it fails. That single change converts the blind 4^L enumeration into a sharply pruned DFS, and reusing the board itself as the visited marker removes the extra matrix.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
board = [["A","B"],["C","D"]], word = "AC"Interactive diagram
Blind enumeration starts everywhere
start (0,0)='A'Without a first-letter prune, full walks are launched even from cells that can't begin the word (red), and matches are only checked at the leaves.
true — but only after launching doomed walks from non-'A' cellsC · Code with teaching comments
Reference implementation preview// Illustrative — enumerate paths, compare at the end, fresh visited per start. public boolean exist(char[][] board, String word) { int m = board.length, n = board[0].length; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) {Explore the full codeHide the full code
D · Why it works and complexityO(m·n·4^L) with poor constants timeO(m·n) visited matrix per call + O(L) recursion spaceOpen the invariant and proofExplore the proofHide the proof
Generate-all-paths-then-compare separates 'walk' from 'check'. The optimal DFS fuses them — it refuses to extend a path the moment a letter disagrees — which prunes the overwhelming majority of branches before they grow.
ComplexityO(m·n·4^L) with poor constants time, O(m·n) visited matrix per call + O(L) recursion space — From each of m·n cells you branch up to 4 ways for L levels (4^L paths), and checking the match only at the end means mismatched prefixes are explored fully; a freshly allocated visited matrix per start adds more overhead.
E · Edge cases and pitfalls4board = [["A"]], word = "A" — Single cell matches at full length 1 → returns true. Works, but the lack of a first-letter prune is irrelevant only because the grid is 1×1.Explore edge casesHide edge cases
Edge cases handled
board = [["A"]], word = "A"Single cell matches at full length 1 → returns true. Works, but the lack of a first-letter prune is irrelevant only because the grid is 1×1.
Pitfalls
- Comparing the path string only at full length means mismatched prefixes are explored completely.
- Allocating a fresh visited matrix per starting cell churns memory unnecessarily.
- No first-letter prune launches full walks from cells that can't start the word.
Approach 2 of 2 · Optimal
DFS + Backtracking with In-Place Marking (Optimal)
1Hint 1Explore hintHide hint
Validate the letter match at the TOP of the recursion: if this cell is out of bounds or doesn't equal word[k], return false immediately. That single guard prunes most branches.
2Hint 2Explore hintHide hint
Before recursing into neighbours, overwrite the current cell with a sentinel like '#' so the same path can't step on it again; put the original letter back after the recursion (backtrack).
3Hint 3Explore hintHide hint
Short-circuit: return true as soon as any of the 4 neighbour calls succeeds. Only start a DFS from cells equal to word[0]; optionally search for the rarer end of the word first.
A · Core idea
Run a DFS from every cell, indexing into word by depth k. At the top of each call: if out of bounds or board[r][c] != word[k], return false. If k has reached word.length(), we've matched every letter — return true. Otherwise choose the cell (overwrite it with '#'), explore the 4 neighbours with k + 1, then un-choose (restore the original letter), returning true if any neighbour succeeded.
Why mark the cell — and why restore it. The rule 'no cell reused in a path' means while we're standing on a cell, the rest of this path must treat it as off-limits. Overwriting it with '#' (which never equals any real letter) makes the top-of-function letter check reject it automatically — no separate visited matrix needed. But the cell is only off-limits for the current path: a different path should be free to use it. So the moment the recursion returns, we restore the original letter. That restore IS the backtracking discipline — skip it and a cell consumed on one dead-end branch stays permanently blocked, producing false negatives.
Why check the match at the top, not before recursing. Guarding inside the function (bounds + letter) makes the recursion self-validating: the caller can fire all four neighbour calls blindly and let each one reject itself. That keeps the code symmetric and bug-free versus pre-checking each neighbour at the call site.
Why short-circuit and where to prune. As soon as one neighbour returns true, the word exists — stop. We only launch a DFS where board[r][c] == word[0], skipping doomed starts. A strong extra: count letter frequencies in the board versus the word and bail early if the board lacks enough of some letter; and if word[0] is more common than word[-1], reverse word so the search tree branches less at the root. These don't change the big-O but slash real runtimes.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"Array state
(0,0), k=0
'A' matches → mark '#'
trueC · Code with teaching comments
D · Why it works and complexityO(m·n·4^L) timeO(L) spaceOpen the invariant and proofExplore the proofHide the proof
The in-place '#' marker turns the board itself into the visited set, so backtracking is just 'save letter → recurse → write letter back'. The save/restore pair is the universal grid-backtracking move; once you trust it, every maze/island/word-path problem is the same skeleton with a different success test.
ComplexityO(m·n·4^L) time, O(L) space — Each of m·n cells can launch a DFS; each DFS branches into at most 3 new directions (one neighbour is where we came from) for L levels, giving O(m·n·4^L) worst case. Space is just the recursion stack of depth ≤ L — the in-place '#' marking means no extra visited matrix, so O(L).
E · Edge cases and pitfalls5board = [["a"]], word = "a" — Start matches word[0]; DFS marks '#', then k+1 == len(word) on the next call → returns true. Single-cell word handled by the base case.Explore edge casesHide edge cases
Edge cases handled
board = [["a"]], word = "a"Start matches word[0]; DFS marks '#', then k+1 == len(word) on the next call → returns true. Single-cell word handled by the base case.board = [["A","B"],["C","D"]], word = "ABCB"A→B→C reaches the second 'B' but the only 'B' cell is already '#', so the letter check fails, the branch unwinds restoring cells, and all starts fail → false.
Pitfalls
- Forgetting to restore the cell after recursion — a consumed letter stays blocked and causes false negatives.
- Putting the bounds/match check at the call site instead of the top of the DFS — leads to asymmetric, buggy guards.
- Not short-circuiting on the first successful neighbour — wastes work after the answer is already known.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean exist(char[][] board, String word) { int m = board.length, n = board[0].length; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { if (board[r][c] == word.charAt(0) && dfs(board, word, r, c, 0)) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Forgetting to restore the cell (no backtrack)
If you mark a cell '#' but never write the letter back, the cell stays blocked for every other path. A valid word that needs that cell on a different route is reported missing.
Explore the code comparisonHide the code comparison
Forgetting to restore the cell (no backtrack)
If you mark a cell '#' but never write the letter back, the cell stays blocked for every other path. A valid word that needs that cell on a different route is reported missing.
Don't write this
board[r][c] = '#'
found = (dfs(r+1, c, k+1) or dfs(r-1, c, k+1)
or dfs(r, c+1, k+1) or dfs(r, c-1, k+1))
return found # cell never restored!Write this instead
tmp = board[r][c]
board[r][c] = '#'
found = (dfs(r+1, c, k+1) or dfs(r-1, c, k+1)
or dfs(r, c+1, k+1) or dfs(r, c-1, k+1))
board[r][c] = tmp # restore — the backtracking step
return found2No visited-marking at all
Without marking the current cell, the recursion can step back onto it, reusing one cell to satisfy two letters — wrongly matching words like 'ABCB' through a single 'B'.
Explore the code comparisonHide the code comparison
No visited-marking at all
Without marking the current cell, the recursion can step back onto it, reusing one cell to satisfy two letters — wrongly matching words like 'ABCB' through a single 'B'.
Don't write this
if board[r][c] != word[k]:
return False
return (dfs(r+1, c, k+1) or dfs(r-1, c, k+1) # may re-enter (r,c)
or dfs(r, c+1, k+1) or dfs(r, c-1, k+1))Write this instead
if board[r][c] != word[k]:
return False
tmp, board[r][c] = board[r][c], '#' # block reuse this path
ok = (dfs(r+1, c, k+1) or dfs(r-1, c, k+1)
or dfs(r, c+1, k+1) or dfs(r, c-1, k+1))
board[r][c] = tmp
return ok3Checking bounds at the call site
Pre-validating each neighbour before recursing duplicates logic four times and is error-prone. Guard once at the top of the DFS so the recursion is self-validating.
Explore the code comparisonHide the code comparison
Checking bounds at the call site
Pre-validating each neighbour before recursing duplicates logic four times and is error-prone. Guard once at the top of the DFS so the recursion is self-validating.
Don't write this
if (r + 1 < m && board[r+1][c] == word.charAt(k+1)) dfs(board, word, r+1, c, k+1);
if (c + 1 < n && board[r][c+1] == word.charAt(k+1)) dfs(board, word, r, c+1, k+1);Write this instead
if (r < 0 || c < 0 || r >= m || c >= n || board[r][c] != word.charAt(k)) return false;
// ...then recurse into all 4 neighbours unconditionallyRevise
Carry the pattern into the interview
Pattern to remember
Grid DFS + backtracking (choose → explore → un-choose) with visited-marking
Code pattern to memorize
def dfs(r, c, k):
if k == len(word): return True
if out_of_bounds or board[r][c] != word[k]: return False
tmp, board[r][c] = board[r][c], '#' # choose / mark visited
found = any(dfs(r+dr, c+dc, k+1) for 4 dirs) # explore
board[r][c] = tmp # un-choose / restore
return foundRules to remember
- 1Mark the current cell visited before recursing and restore it after — the restore is what lets sibling paths legally reuse the cell.
- 2Use the in-place '#' (sentinel) trick to avoid a separate visited matrix; just remember to put the original letter back.
- 3Check bounds and the letter match at the top of the DFS so the recursion is self-guarding — callers don't pre-validate neighbours.
- 4Return
Trueimmediately on the first successful neighbour (short-circuit); don't keep exploring once the word is found. - 5Launch a DFS from every cell — the word can start anywhere; prune by only starting where
board[r][c] == word[0].
Use this pattern when
- Search a grid/matrix for a path matching a sequence under adjacency rules
- Each cell may be used at most once per path (need visited-marking)
- Exploring connected neighbours (4- or 8-directional) with the option to abandon dead branches
- 'Does a path exist?' or 'find/count paths' on a 2-D board
Choose another pattern when
- Cells can be revisited freely → plain BFS/DFS reachability, no backtracking restore needed
- Searching for MANY words at once → build a Trie (that's Word Search II)
- Shortest path / fewest steps → BFS, not exhaustive DFS
- No adjacency constraint, just membership → hash set, not a grid walk
Interview takeaway
Word Search is the canonical grid-backtracking problem: DFS with mark-on-enter / restore-on-exit. The same choose/explore/un-choose discipline drives Number of Islands variants, Word Search II (add a Trie), and rat-in-a-maze path problems. The restore step is the one line beginners forget and the one interviewers watch for.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Grid DFS + Backtracking (choose → explore → un-choose) with in-place visited-marking. Recognise it whenever you trace a path through a matrix under adjacency and no-reuse rules. The mark-on-enter / restore-on-exit skeleton also drives Word Search II (add a Trie), rat-in-a-maze, and unique-path enumeration problems.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Word Search IIComing soonMany words at once → build a Trie of the word list and DFS the grid once, pruning by Trie nodes instead of restarting per word.
- Number of IslandsComing soonSame 4-directional grid DFS, but flood-fill connected land — no backtracking restore since cells stay consumed.
- Surrounded RegionsComing soonDFS from the borders marking reachable cells, then flip the rest — grid traversal with sentinel marking, like the '#' trick.
- Longest Increasing Path in a MatrixComing soonGrid DFS again, but add memoization since paths can be revisited freely (no no-reuse constraint) — DFS + cache, not backtracking.