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.

board[r][c] = '#'      # mark
... recurse ...
board[r][c] = letter   # undo

No 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.

Think of this like exploring a maze and dropping a heavy sandbag (#) on the tile you are currently standing on before taking your next step. If you wander in a circle and see a sandbag, you immediately know you've already been there on this exact trip. If you hit a dead end and need to back up, you pick up the sandbag as you step backwards, leaving the tile clean for a completely different path to explore later.

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 False

TypeScript

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.

Let's break this down:

• Time Complexity: We initiate a DFS from every single cell, so there are M \times N starting points. For each DFS, the maximum depth is L (the length of the word). At the first step, we have 4 choices. For the remaining L-1 steps, we have at most 3 choices (because we can't go backwards to the cell we just left). This gives an upper bound of O(M \cdot N \cdot 4 \cdot 3^{L-1}). In reality, most paths die on the first or second step due to mismatched letters.
• Space Complexity: The only extra space is the recursive call stack. The recursion goes exactly L levels deep before stopping or finding the word, which takes O(L) space. Modifying the board in-place saves us an O(M \times N) visited matrix.

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.