158. Word Search in Grid

Why this mechanism works

Unlike flood fill, a cell's availability belongs to the current candidate path. A globally permanent visited set would incorrectly exclude cells from later starting points. Match one character, reserve that cell, explore the next character, then release the cell even after a successful branch. The recursive contract includes both location and word position.

State and boundaries

used contains exactly the cells reserved by earlier matched characters. visit(r,c,i) asks whether word[i:] can begin at this unused cell.

Protocol

1. Accept an empty word.
2. Try every cell as a start.
3. Reject out-of-bounds, used or mismatching cells.
4. Accept a matching final character.
5. Reserve the current cell, explore four neighbors, release it, and return the result.

Visualization

A B C
D E F
word ABE: (0,0) -> (0,1) -> (1,1)
used is local to this route, then restored

Python implementation

def word_exists(board, word):
    if not word:
        return True
    if not board or not board[0]:
        return False
    rows, cols = len(board), len(board[0])
    used = set()
    def visit(r, c, i):
        if not (0 <= r < rows and 0 <= c < cols):
            return False
        if (r, c) in used or board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        used.add((r, c))
        found = any(visit(r + dr, c + dc, i + 1)
                    for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)))
        used.remove((r, c))
        return found
    return any(visit(r, c, 0) for r in range(rows) for c in range(cols))

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 word_exists: if not word:
board=[['A', 'B', 'C'], ['D', 'E', 'F']]; word='ABE'

L6 word_exists: rows, cols = len(board), len(board[0])
board=[['A', 'B', 'C'], ['D', 'E', 'F']]; word='ABE'; cols=3; rows=2

L7 word_exists: used = set()
board=[['A', 'B', 'C'], ['D', 'E', 'F']]; word='ABE'; cols=3; rows=2; used=set()

L9 visit: if not (0 <= r < rows and 0 <= c < cols):
r=0; c=0; i=0; board=[['A', 'B', 'C'], ['D', 'E', 'F']]; cols=3; rows=2; used=set(); word='ABE'

L15 visit: used.add((r, c))
r=0; c=0; i=0; board=[['A', 'B', 'C'], ['D', 'E', 'F']]; cols=3; rows=2; used={(0, 0)}; word='ABE'

L16 <genexpr>: found = any(visit(r + dr, c + dc, i + 1)
.0=tuple_iterator; c=0; i=0; r=0

L17 <genexpr>: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)))
.0=tuple_iterator; c=0; i=0; r=0; dr=1; dc=0

L9 visit: if not (0 <= r < rows and 0 <= c < cols):
r=1; c=0; i=1; board=[['A', 'B', 'C'], ['D', 'E', 'F']]; cols=3; rows=2; used={(0, 0)}; word='ABE'

... 9 intermediate state changes omitted ...

L18 visit: used.remove((r, c))
r=0; c=1; i=1; board=[['A', 'B', 'C'], ['D', 'E', 'F']]; cols=3; rows=2; used={(0, 0)}; word='ABE'; found=True

L16 visit: found = any(visit(r + dr, c + dc, i + 1)
r=0; c=0; i=0; board=[['A', 'B', 'C'], ['D', 'E', 'F']]; cols=3; rows=2; used={(0, 0)}; word='ABE'; found=True

L18 visit: used.remove((r, c))
r=0; c=0; i=0; board=[['A', 'B', 'C'], ['D', 'E', 'F']]; cols=3; rows=2; used=set(); word='ABE'; found=True

L20 <genexpr>: return any(visit(r, c, 0) for r in range(rows) for c in range(cols))
.0=range_iterator; r=0; c=0; cols=3

L2 word_exists: if not word:
board=[['A', 'B']]; word='ABA'

L6 word_exists: rows, cols = len(board), len(board[0])
board=[['A', 'B']]; word='ABA'; cols=2; rows=1

L7 word_exists: used = set()
board=[['A', 'B']]; word='ABA'; cols=2; rows=1; used=set()

L9 visit: if not (0 <= r < rows and 0 <= c < cols):
r=0; c=0; i=0; board=[['A', 'B']]; cols=2; rows=1; used=set(); word='ABA'

L15 visit: used.add((r, c))
r=0; c=0; i=0; board=[['A', 'B']]; cols=2; rows=1; used={(0, 0)}; word='ABA'

L16 <genexpr>: found = any(visit(r + dr, c + dc, i + 1)
.0=tuple_iterator; c=0; i=0; r=0

L17 <genexpr>: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)))
.0=tuple_iterator; c=0; i=0; r=0; dr=1; dc=0

L9 visit: if not (0 <= r < rows and 0 <= c < cols):
r=1; c=0; i=1; board=[['A', 'B']]; cols=2; rows=1; used={(0, 0)}; word='ABA'

... 22 intermediate state changes omitted ...

L20 <genexpr>: return any(visit(r, c, 0) for r in range(rows) for c in range(cols))
.0=range_iterator; r=0; c=0; cols=2

L9 visit: if not (0 <= r < rows and 0 <= c < cols):
r=0; c=1; i=0; board=[['A', 'B']]; cols=2; rows=1; used=set(); word='ABA'

L20 <genexpr>: return any(visit(r, c, 0) for r in range(rows) for c in range(cols))
.0=range_iterator; r=0; c=1; cols=2

L20 <genexpr>: return any(visit(r, c, 0) for r in range(rows) for c in range(cols))
.0=range_iterator; r=0; c=1; cols=2

Why the solution is correct

A successful call matches its current character and extends through adjacent distinct cells by the recursive contract. Every valid path has a starting cell and a sequence of neighbor choices the search explores. Releasing reservations restores sibling state. The word index advances, bounding depth.

Time and space

O(R*C*4^L) coarse worst-case time for word length L; O(min(L,R*C)) auxiliary path/set and stack, excluding input.

Common mistakes

Permanent visitation confuses reachability with path enumeration. Returning immediately after a recursive success without cleanup is dangerous when mutable state is reused.

Reasoning card

Transfer exercise

Search for many words together with a trie. Which shared prefixes would avoid repeating the same board exploration?