79. Word Search

Word Search is the grid problem that makes backtracking click: you wander through a board of letters, and the moment a path stops spelling the word, you rewind and try another direction. It’s a textbook case of the backtracking pattern — the trick is knowing exactly what state to undo when a branch fails.

The problem

You’re given a grid of characters and a target word. Return true if the word can be traced through the grid by stepping between cells that share an edge (up, down, left, right), never reusing the same cell within one path. (Full statement on LeetCode.)

Take this 3×3 board and the word "CAT":

C A B
X T S
D O G

Start at the top-left C, step right to A, then down to T — that spells CAT, so the answer is true.

Intuition: try every start, then follow the letters

There’s no shortcut to picking the right starting cell, so you try them all. From each cell that matches word[0], launch a depth-first search that asks the same question one letter deeper: does a neighbor match the next character? If yes, recurse; if you run out of grid, hit a mismatch, or bump into a cell you’re already standing on, that branch dies and you back out.

The one piece of state that matters is “cells used by the current path.” Instead of a separate visited set, you can mark a cell in place — overwrite it with a sentinel like # before recursing, then restore it after. That restore is the whole soul of backtracking: the cell is off-limits only while it’s part of the path you’re exploring, and it becomes available again the instant you leave, so a different route can reuse it.

Why the four DFS branches never double-count: each is a strictly deeper call into a longer prefix, and the mismatch check at the top of every call prunes anything that stops spelling the word. The branching factor is at most 4 (one direction is where you came from, already marked), so a word of length $L$ costs $O(4^L)$ in the worst case per start, and there are $m \cdot n$ starts.

Solution

Every DFS call takes the current cell and the index into word it’s trying to match. The base cases come first, then the mark-recurse-restore dance:

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length, cols = board[0].length;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(board, word, r, c, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int r, int c, int i) {
        if (i == word.length()) return true;              // matched every letter
        if (r < 0 || r >= board.length ||
            c < 0 || c >= board[0].length) return false;  // walked off the grid
        if (board[r][c] != word.charAt(i)) return false;  // wrong letter (also blocks '#')

        char saved = board[r][c];
        board[r][c] = '#';                                // claim this cell for the path

        boolean found = dfs(board, word, r + 1, c, i + 1)
                     || dfs(board, word, r - 1, c, i + 1)
                     || dfs(board, word, r, c + 1, i + 1)
                     || dfs(board, word, r, c - 1, i + 1);

        board[r][c] = saved;                              // release it on the way out
        return found;
    }
}

Marking with # does double duty: it stops the path from stepping back onto itself, and since # never equals any real letter, the mismatch check already rejects a revisit for free — no extra bookkeeping. The || chain short-circuits, so the first direction that completes the word stops the search immediately.

Complexity

	Time	Space
DFS backtracking	$O(m \cdot n \cdot 4^L)$	$O(L)$

Here $m \times n$ is the grid size and $L$ is the word length. Every cell is a potential start, and each DFS chases up to 4 directions per letter. Space is the recursion depth, which never exceeds $L$ since the path can’t be longer than the word.

In an interview

Say the plan out loud before coding: “I’ll try each cell as a start, DFS in four directions, mark visited cells in place, and restore them when I backtrack.” The line interviewers listen for is why you restore the cell — leave it out and you’ve built a one-shot flood fill that permanently burns every cell it touches, so a valid word sharing letters across branches fails. Mention it explicitly.

The classic edge case is a repeated letter, like searching "AAB" on a board full of As: the in-place mark is exactly what stops the same A from satisfying two positions at once. If they push on speed, the follow-up is pruning — bail early if the board doesn’t even contain enough of some letter in word. This is the same choose-explore-unchoose skeleton behind Combination Sum; the backtracking hub walks through where the shape repeats.

References

• LeetCode 79 — Word Search