Core Insight Build one partial answer at a time and undo each choice so sibling branches start clean.
Common Pitfall Copy a completed path before appending it to results; later mutations must not alter it.
Description
Check if a word exists in the grid.
Constraints
- Time Complexity:
O(4^n) - Space Complexity:
O(n)
Tags
arraystringbacktrackingmatrix
Implementation Plan Translate the invariant into these small, testable moves.
- Choose a candidate.
- Record the choice.
- Explore the next decision.
- Undo the choice before trying the next candidate.
def exist(board, word):
ROWS, COLS = len(board), len(board[0])
path = set()
def dfs(r, c, i):
if i == len(word):
return True
if (r < 0 or c < 0 or r >= ROWS or c >= COLS or
word[i] != board[r][c] or (r, c) in path):
return False
path.add((r, c))
res = (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))
path.remove((r, c))
return res
for r in range(ROWS):
for c in range(COLS):
if dfs(r, c, 0): return True
return False