Word Search — Solution

Problem

Given a 2D grid of characters and a target word, determine whether the word can be formed by following a path of adjacent cells — horizontally or vertically — where no cell may be used more than once in a single path.

• Input: the board above, word = "ABCCED"
• Output: true
• Explanation: the path A(0,0) → B(0,1) → C(0,2) → C(1,2) → E(2,2) → D(2,1) spells the word

Counter-example: word = "ABCB" returns false — after reaching B at (0,1), there is no way to get back to B without reusing the cell.

Intuition

This is a search problem with a "no revisiting" constraint, which makes it a natural fit for backtracking. The key insight is that the board state changes as we walk a path — we temporarily mark cells visited — and then we restore the board when we retreat, so other paths can use those cells. There is no smarter algorithm than trying every valid path; the gains come from cutting off failed paths as early as possible.

Solution — Backtracking DFS

For every cell that matches the first character of the word, launch a depth-first search. At each step, check bounds, the current character, and whether the cell is already on the active path. Mark the cell to prevent reuse, recurse into all four neighbors, then restore the cell before returning so other paths can use it.

1. Scan every cell; when board[r][c] matches word[0], call backtrack(r, c, 0).
2. In backtrack: if index == len(word), all characters matched — return True.
3. Return False immediately if out of bounds or the cell doesn't match word[index] (this also catches the visited marker '#' since '#' is never a letter).
4. Save the current character, then overwrite the cell with '#' to mark it visited.
5. Recurse into the four neighbors with index + 1; combine results with or (short-circuits on first True).
6. Restore the cell to its saved character before returning — this is the backtrack step.

1def exist(board: list[list[str]], word: str) -> bool:
2    rows, cols = len(board), len(board[0])
3
4    def backtrack(r: int, c: int, index: int) -> bool:
5        if index == len(word):
6            return True  # every character in word has been matched
7        if r < 0 or r >= rows or c < 0 or c >= cols:
8            return False
9        if board[r][c] != word[index]:
10            return False  # wrong character, or '#' sentinel from a visited cell
11
12        original_char = board[r][c]
13        board[r][c] = '#'  # mark visited to block reuse on this path
14
15        found = (backtrack(r + 1, c, index + 1) or
16                 backtrack(r - 1, c, index + 1) or
17                 backtrack(r, c + 1, index + 1) or
18                 backtrack(r, c - 1, index + 1))
19
20        board[r][c] = original_char  # restore cell so other paths can use it
21        return found
22
23    for r in range(rows):
24        for c in range(cols):
25            if backtrack(r, c, 0):
26                return True
27
28    return False

Time: O(m × n × 4^L) — from each of the m×n starting cells the DFS explores at most 4^L paths (L = word length); in practice much faster because mismatched characters prune branches immediately.

Space: O(L) — the recursion call stack goes at most L frames deep, one per character in the word.

Complexity Summary

Common Mistakes

• Not restoring the cell after backtracking — if you mark a cell '#' but never reset it, cells used in one failed path stay marked and are unavailable to paths starting from other cells, causing false false results.
• Checking board[r][c] before validating bounds — accessing an out-of-bounds index throws an error; always check r and c against the grid dimensions before touching board[r][c].
• Marking the cell visited after the recursive calls instead of before — a neighbor can then recurse back into the current cell and reuse it, producing incorrect paths where the same cell appears twice.
• Returning True when index == len(word) - 1 and checking the character at the same time — the cleaner base case is if index == len(word): return True at the top of the function, checked before any bounds or character validation; this avoids the off-by-one where you also need to confirm the last character matches.
• Using or with four separate if statements that all return early — if the first direction returns True, the early return is correct, but if you structure it as four independent if backtrack(...): return True blocks without the or, you may forget that a failed branch should not immediately return False — you need to try all four before giving up.

Related Problems

• Word Search II — extends this to finding all words from a list simultaneously using a Trie to avoid redundant paths
• Number of Islands — the same DFS flood-fill skeleton on a grid, but without the character-matching or backtracking requirement
• Path Sum II — backtracking on a tree to collect all root-to-leaf paths that hit a target, same mark-recurse-unmark pattern
• N-Queens — classic backtracking with a constraint check before placing each piece, same shape as checking word[index] before recursing
• Combination Sum II — backtracking over a flat list with a "no reuse" constraint, analogous to the visited-cell restriction here