The tell: A path through a grid matching a sequence, where cells cannot be reused within a path.
How you get there
1DFS from each cell, matching one character per step.
2Mark the cell during the path so it cannot be reused, then restore it.
3Prune immediately when the character does not match.
Solution
Python
def exist(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
if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[k]:
return False
board[r][c] = "#" # mark for this path only
found = any(
dfs(r + dr, c + dc, k + 1)
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1))
)
board[r][c] = word[k] # restore
return found
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))
Time
O(cells · 4^L)
Space
O(L)
What goes wrong
A global visited set instead of per-path marking wrongly blocks cells for later starting positions.