Appearance
4.18.6 — Word Search
LeetCode 79 · Medium · ★ Blind 75
The problem
Return true if the word can be spelled by walking through adjacent cells of the grid — up, down, left or right. A cell cannot be used twice in the same word.
board = [["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]]
word = "ABCCED" → true
word = "SEE" → true
word = "ABCB" → false (the B would have to be reused)Up to a 6×6 grid, word up to 15 characters.
The pattern
Backtracking again, but the "choices" are now directions on a grid rather than elements of a list.
At each step you are standing on a cell, matching character k of the word. The choices are the four neighbours. The constraints are:
- stay inside the grid,
- the cell has not been used on this path,
- the letter matches the next character.
Start the search from every cell, because the word could begin anywhere.
The neat part: the board is the visited set
You need to know which cells the current path has used. The obvious answer is a separate visited grid, and that works.
But there is a cheaper one: overwrite the cell with a character that cannot match anything, then restore it on the way out.
python
board[r][c] = '#' # mark
... recurse ...
board[r][c] = letter # undoNo extra memory, and the check "is this cell used" becomes the same comparison as "does this letter match" — a used cell holds #, which never equals a word character.
The restore is the backtracking step, and it is exactly the path.pop() of the list problems, applied to a grid.
The solution
python
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
def dfs(r: int, c: int, k: int) -> bool:
if k == len(word):
return True # matched everything
if r < 0 or r >= rows or c < 0 or c >= cols:
return False # off the grid
if board[r][c] != word[k]:
return False # wrong letter, or already used
letter = board[r][c]
board[r][c] = '#' # mark visited
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] = letter # undo
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return Falsets
function exist(board: string[][], word: string): boolean {
const rows = board.length, cols = board[0].length;
function dfs(r: number, c: number, k: number): boolean {
if (k === word.length) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
if (board[r][c] !== word[k]) return false;
const letter = board[r][c];
board[r][c] = '#';
const found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1)
|| dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
board[r][c] = letter;
return found;
}
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (dfs(r, c, 0)) return true;
return false;
}Four details.
Check k == len(word) before the bounds check. The word may end exactly as the walk reaches the grid edge; testing bounds first would reject a valid match.
board[r][c] != word[k] catches two failures at once — a wrong letter and a cell already on this path, since a used cell holds #.
Save the letter in a local before overwriting. By the time you restore it, the board no longer holds it.
or short-circuits, so as soon as one direction succeeds the rest are skipped — and the restore still runs, because it is after the assignment rather than inside a return.
Writing return dfs(...) or dfs(...) or ... directly would skip the restore entirely and leave the board corrupted for the next starting cell. Assigning to found and restoring before returning is what makes it correct, and it is the most common bug in this problem.
Complexity
O(\text{cells} \times 4 \times 3^{L-1}) where L is the word length. From the first cell there are 4 directions; after that only 3, because you never step back onto the cell you came from.
In practice it is far less, because a wrong letter kills a branch immediately.
O(L) space for the recursion, and O(1) extra beyond that thanks to marking the board in place.
Small optimisations worth naming
Count the letters first. If the board does not contain enough of some letter in the word, return false without searching at all.
Search from the rarer end. If the word's last letter appears less often on the board than its first, reverse the word before searching. Fewer starting cells means less work. This is a genuinely clever one to volunteer.
Neither changes the asymptotic bound; both change the constant substantially on adversarial inputs.
Where this goes next
- Word Search II — many words at once, using a trie so that one grid walk explores all of them. 4.15.3. The connection is worth stating: this problem run in a loop is too slow, and the trie is what fixes it.
- Number of Islands — grid DFS without backtracking. Cells are marked visited and never restored, because you are counting regions rather than finding paths. 4.20.
That contrast is the thing to take away. Both walk a grid with DFS. Whether you undo the visited mark depends on the question:
- Finding a path — undo, because a cell blocked for this path must be free for another.
- Finding or counting regions — do not undo, because a cell belongs to exactly one region and revisiting it is pure waste.
Getting that backwards is the most common grid-search mistake, in both directions.
What the interviewer will push on
"How do you track visited cells?" Mark the board itself, and restore on the way out.
"Why restore?" A cell used by one path must be available to a different path.
"Why is it 3^{L-1} and not 4^L?" You never step back the way you came.
"What if you had many words?" Build a trie and walk the grid once — Word Search II.
"How is this different from Number of Islands?" Paths undo the mark; regions do not.
One thing to volunteer: mention searching from the rarer end of the word. It is a small, real optimisation that shows you thought about the input rather than only the algorithm.
Next: 4.18.7 Palindrome Partitioning — the same start-index loop, where the choice is where to cut a string.