Word Search
Given an `m × n` grid of characters `board` and a string `word`, return `true` if `word` exists in the grid. The word must be constructed from letters of sequentially adjacent cells (horizontally or vertically adjacent). The same cell may not be used more than once. **Core Insight:** Backtracking DFS. For each cell that matches `word[0]`, launch a DFS that tries to match the remaining characters by exploring all 4 neighbours. Mark the current cell as visited before recursing (e.g. temporarily set it to `#`) and restore it after backtracking. **Algorithm:** For each cell `(r, c)`: if `board[r][c] == word[0]` call `dfs(r, c, 0)`. In `dfs(r, c, idx)`: if `idx == len(word)` return true. If out of bounds, already visited, or `board[r][c] != word[idx]` return false. Mark visited, recurse on 4 neighbours, unmark, return result. **Pruning:** Return early as soon as a valid path is found. The backtracking ensures we explore all possibilities without reusing cells. **Complexity:** Time O(m × n × 4^L) where L is the word length. Space O(L) — recursion stack depth.
Constraints
- •
m == board.length - •
n == board[i].length - •
1 ≤ m, n ≤ 6 - •
1 ≤ word.length ≤ 15
def exist(board: list[list[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
def dfs(r, c, idx):
if idx == len(word): return True
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[idx]: return False
tmp, board[r][c] = board[r][c], '#'
found = dfs(r+1,c,idx+1) or dfs(r-1,c,idx+1) or dfs(r,c+1,idx+1) or dfs(r,c-1,idx+1)
board[r][c] = tmp
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0): return True
return False