LeetCode #79 Medium

Word Search

Given a grid of characters and a word, decide whether the word can be spelled by walking through horizontally or vertically adjacent cells without reusing a cell.

backtrackingmatrixdfsarray

Open on LeetCode ↗

02

Intuition

You will mark a cell visited so the path cannot walk back onto itself, and then you will forget to un-mark it when the path fails. That one missing line is what this problem exists to teach. Picture searching for SEE and starting at the wrong S: the walk marks four cells, dead-ends, and returns false — but those four cells are still flagged. When the correct anchor starts its search and needs one of them, the grid lies and says it is occupied, so a word that is genuinely on the board reports false. A failed attempt has poisoned the board for everyone after it. The fix is to restore the cell as the recursion unwinds: mark, recurse over the four neighbours, un-mark. That restore IS the backtracking; the DFS is just how you get around. The invariant is that a cell is marked used exactly while it sits on the path currently being explored, so the board is bit-for-bit identical every time control returns to a caller — which is the only reason each new anchor gets a fair search.

How to spot this pattern

DFS with in-place marking: overwrite the cell with a sentinel before recursing, restore it after. That single mutation enforces "no cell reused within one path" without a visited set, and restoring on the way out is what lets other paths use the cell.

03

Approach

1

Try every cell as an anchor

Any cell holding the word's first letter could start a valid path, so scan the whole grid and launch a DFS from each match. Return true on the first success — this is an existence question, not a counting one, so there is nothing to gain from continuing once a path is found.

2

DFS with a matching index

The search carries the index of the letter it currently needs. Reject immediately if the position is off the grid, already on the path, or holds the wrong character; succeed when the index reaches the last letter. Checking the character before recursing is what keeps this near-linear in practice — a mismatch kills the branch at depth one rather than after exploring it.

3

Mark, recurse, restore

Before exploring the neighbours, overwrite the cell with a sentinel such as '#' so the path cannot revisit it. After all four neighbours have been tried and failed, write the original character back. Using the grid itself as the visited set costs no extra space, but it makes the restore non-negotiable — skip it and you have not just lost information, you have corrupted the input.

04

Solution & live demo

▶1class Solution:
▶2    def exist(self, board: list[list[str]], word: str) -> bool:
▶3        R, C = len(board), len(board[0])
▶4        if len(word) > R * C:
▶5            return False
▶6 
▶7        def dfs(r: int, c: int, k: int) -> bool:
▶8            if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[k]:
▶9                return False
▶10            if k == len(word) - 1:
▶11                return True
▶12 
▶13            tmp = board[r][c]
▶14            board[r][c] = '#'
▶15            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
▶16                if dfs(r + dr, c + dc, k + 1):
▶17                    return True
▶18            board[r][c] = tmp
▶19            return False
▶20 
▶21        for r in range(R):
▶22            for c in range(C):
▶23                if board[r][c] == word[0]:
▶24                    if dfs(r, c, 0):
▶25                        return True
▶26        return False

05

Common pitfalls

Not restoring the cell before returning false

✗ Wrong

board[r][c] = '#'
for ...: if dfs(...): return True
return False

✓ Right

board[r][c] = '#'
for ...: if dfs(...): return True
board[r][c] = tmp
return False

A failed path must leave the board exactly as it found it. Without the restore, cells stay permanently blocked and later searches starting elsewhere fail on a board that should still work.

Using a shared visited set across start positions

✗ Wrong

visited = set()   # created once, outside the loops

✓ Right

board[r][c] = '#'   # per-path, restored on unwind

The constraint is per-path, not global — a cell used by one attempted path must be available to the next. A set that's never cleared makes every start after the first search a crippled board.

Checking bounds at the call site

✗ Wrong

if 0 <= nr < R and 0 <= nc < C:
    dfs(nr, nc, k + 1)

✓ Right

if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[k]:
    return False

Guarding at each of the four call sites duplicates the condition and is easy to get inconsistent. Testing once at the top of the function covers every entry path including the initial call.

06

Edge cases

Word longer than the number of cells

It cannot possibly fit; every path exhausts its options and the scan returns false. A length check up front short-circuits it in O(1).

Single-character word

The base case fires on the anchor itself before any neighbour is examined, so the answer is simply whether that character appears anywhere in the grid.

A path that must reuse a cell, e.g. ABCB on a board where the second B is the first one

The visited mark blocks the revisit, the branch dies, and the answer is correctly false — reuse is forbidden by the problem.

The word starts on a cell that dead-ends

The failed branch un-marks every cell it touched on the way out, so the next anchor searches a fully restored board. This is the exact scenario the restore protects.

07

Complexity

Time

O(R * C * 3^L)

Space

O(L)

L is the word length; each step has three onward directions rather than four because you never walk straight back into the cell you came from, which is already marked.