Word Search: Grid Backtracking

You are given an m x n grid of characters and a target word. Return True if the word exists in the grid, where the word can be constructed from letters of adjacent cells (horizontally or vertically). The same cell cannot be used more than once in a single path.

This is LeetCode 79: Word Search, and it is one of the best problems for learning grid backtracking. Unlike Number of Islands where you permanently mark cells as visited, here you need to undo your visit after exploring a path. That single difference, the "unchoose" step, is what makes this a backtracking problem instead of a simple flood fill.

Why this problem matters

Grid backtracking shows up constantly in interviews. It combines two patterns you need to be fluent in: generating valid grid neighbors and the choose-explore-unchoose template. Word Search is the cleanest introduction to both of those working together. If you can solve this problem from scratch, you can handle virtually any grid backtracking variant that gets thrown at you.

The word search LeetCode problem also forces you to understand why backtracking exists. In flood fill problems, you mark a cell visited and move on forever. In this problem, a cell that is part of one failed path might be part of another successful path. You have to give it back. That is the whole point of unchoosing.

The key insight

For each cell in the grid, try to build the target word starting from that cell using DFS. At each step:

1. Choose: mark the current cell as visited (so we do not loop back to it)
2. Explore: recurse into all four neighbors, looking for the next character
3. Unchoose: unmark the current cell (so other paths can use it)

If any path matches the entire word, return True. If all starting positions fail, return False.

The "unchoose" step is what separates backtracking from plain DFS. In Number of Islands, you sink cells permanently because you never need them again. Here, you restore them because different starting paths might need to pass through the same cell.

The DFS backtracking solution

def exist(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])

    def dfs(r, c, i):
        # Base case: matched all characters
        if i == len(word):
            return True

        # Out of bounds, wrong letter, or already visited
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[i]:
            return False

        # Choose: mark as visited
        temp = board[r][c]
        board[r][c] = "#"

        # Explore: try all four neighbors
        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)
        )

        # Unchoose: restore the cell
        board[r][c] = temp

        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True

    return False

Let's break this down piece by piece.

The outer loop tries every cell as a potential starting position. For each cell, we call dfs(r, c, 0) to try matching from the beginning of the word (index 0).

Inside dfs, we first check the base case: if i == len(word), we have matched every character, so return True. Then we check three failure conditions: out of bounds, wrong letter, or already visited (marked with "#").

The choose step saves the cell's value in temp and replaces it with "#". This prevents the DFS from looping back to this cell during the current path. We then explore all four neighbors, looking for word[i + 1].

The unchoose step is the critical line: board[r][c] = temp. After we finish exploring all paths through this cell, we put its original letter back. This makes the cell available again for other paths originating from different starting positions or different branches of the search tree.

Visual walkthrough

Let's trace through a small grid searching for the word "ABC". Watch how we choose a cell, explore from it, and unchoose it when a path does not work out.

The key moment is the backtracking step. When a path fails (no neighbor matches the next character), we unmark the current cell and return False. The caller then tries the next neighbor. Without the unchoose step, that cell would stay marked as "#" and be unavailable for all future paths.

Why backtracking (unchoose) is needed

This is the most important concept in the problem. Let's look at a concrete example of why you cannot just permanently mark cells.

Consider this grid and the word "ABCB":

A B
C B

Starting at (0,0), we go A(0,0) -> B(0,1). Now we need "C". B's neighbors are A(0,0) (visited) and B(1,1). Neither is "C", so this path fails. But C is at (1,0), a neighbor of A(0,0).

If we permanently marked A(0,0) when we first visited it, the path A(0,0) -> ... would be the only path we ever try from A. We would never find the correct path: start fresh, go A(0,0) -> C(1,0) -> B(1,1) -> ... wait, that does not spell ABCB either. The point is that without unchoosing, entire branches of the search tree get pruned incorrectly. Cells that failed in one branch might succeed in another.

In flood fill (like Number of Islands), permanent marking is correct because you want to visit each cell exactly once. In backtracking, temporary marking is correct because you are searching for a specific path, and the same cell might appear in different candidate paths.

Complexity analysis

Time is O(m * n * 4^L), where m and n are grid dimensions and L is the length of the word. We try each of the m * n cells as a starting point. From each starting cell, the DFS branches into at most 4 directions at each of the L levels. In practice the branching factor is closer to 3 (you do not go back where you came from), and early termination on character mismatches prunes heavily. But the worst case is 4^L per starting cell.

Space is O(L) for the recursion stack. The DFS goes at most L levels deep (one level per character in the word). We modify the board in place, so no extra data structure is needed. If you use a visited set instead, add O(L) for the set as well.

Edge cases

Before submitting, check these:

• Single cell grid, single char word: board = [["A"]], word = "A". Should return True.
• Word longer than grid cells: if len(word) > m * n, return False immediately. No path can possibly be long enough.
• All same characters: board = [["A","A"],["A","A"]], word = "AAAA". Tests that your visited marking works correctly. The path must snake through all four cells.
• First character not in grid: a quick optimization is to check that every character in the word exists in the grid before starting the DFS.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently:

1. Choose-explore-unchoose (backtracking template)

The skeleton that powers all backtracking problems:

def backtrack(state):
    if is_solution(state):
        record(state)
        return

    for choice in candidates(state):
        make_choice(choice)      # choose
        backtrack(state)          # explore
        undo_choice(choice)       # unchoose

In Word Search, make_choice is marking the cell as visited. backtrack is recursing into neighbors. undo_choice is restoring the cell's original letter. This same template powers generating permutations, solving Sudoku, N-Queens, and combination sum problems. The only things that change are what a "choice" is and what "undo" means. The structure is always the same.

This is different from flood fill, where you skip the unchoose step. If the problem says "find if a path exists" or "find all possible arrangements," you probably need backtracking. If it says "mark/count all connected cells," you probably need flood fill.

2. Grid neighbor generation

The same direction-array pattern used in Number of Islands:

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for dr, dc in directions:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        # (nr, nc) is a valid neighbor

In the Word Search solution above, we wrote four separate recursive calls instead of using a direction array. Both approaches work. The direction array version is more compact and extends easily to 8-directional grids. The four-call version can short-circuit with or (skipping remaining neighbors once a match is found). Pick whichever is clearer to you.

Common mistakes

1. Forgetting to unchoose. The most common bug. Without restoring the cell, paths that should succeed get blocked by cells marked during earlier failed attempts. Your code will return False on inputs that should be True.

2. Checking visited status after recursing instead of before. You need to mark the cell before exploring neighbors. Otherwise the DFS can loop back to the current cell through a neighbor, causing infinite recursion.

3. Not short-circuiting the neighbor exploration. Using or between the four recursive calls means we stop as soon as one neighbor succeeds. If you use a loop with any(), make sure you use a generator expression (not a list comprehension), or you will evaluate all four branches even after finding a match.

4. Modifying the board without restoring on the success path. When the DFS returns True, make sure the unchoose step still runs. In the solution above, the restore line board[r][c] = temp executes regardless of whether found is True or False. If you put it inside an else block, the board gets corrupted on success.

When to use this pattern

Look for these signals:

• You need to find a specific path or sequence in a grid or graph
• The same cell or node could appear in multiple candidate paths
• The problem says "exists," "find a path," or "can you construct"
• You need to explore all possibilities but avoid revisiting within a single path

Problems that use the same grid backtracking pattern:

• Word Search II (LeetCode 212): same grid backtracking but with a Trie for multiple words
• Sudoku Solver (LeetCode 37): backtracking with constraint checking at each step
• N-Queens (LeetCode 51): backtracking to place queens row by row
• Path with Maximum Gold (LeetCode 1219): grid backtracking to maximize collected gold

From understanding to recall

You have read through the DFS backtracking solution. You see how choose-explore-unchoose works and why restoring the cell is critical. But can you write the backtracking skeleton and the neighbor generation loop from scratch under interview pressure?

That is the real test. The pattern has specific details that are easy to mix up: saving the cell value before overwriting, restoring it after the recursive calls, checking the base case before the bounds check, using or for short-circuiting. These are not hard concepts. They are recall challenges.

Spaced repetition closes that gap. You practice writing the choose-explore-unchoose template and the grid neighbor loop from memory at increasing intervals. After a few rounds, the pattern is automatic. You see a grid backtracking problem, and the skeleton flows out without hesitation.

The choose-explore-unchoose pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Number of Islands - Grid DFS without backtracking (flood fill). Compare it to Word Search to see exactly when you need the unchoose step and when you do not.
• Maximum Depth of Binary Tree - The simplest DFS recursion problem, a great warm-up before tackling grid DFS
• Climbing Stairs - Teaches the recursive thinking style that makes DFS click

CodeBricks breaks Word Search into its choose-explore-unchoose and grid-neighbor-generation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a grid backtracking problem shows up in your interview, you do not think about it. You just write it.