1. One-Liner
Word Search walks the grid letter-by-letter matching a target word, backtracking when the next letter cannot be continued.
2. The Problem It Solves
Given a 2D grid of letters and a string, determine if the word can be built by moving up/down/left/right from cell to cell, without reusing the same cell in one path (standard LeetCode-style constraint).
3. The Core Idea
From each cell, DFS along the word index: match first character, then recurse to neighbors for the next character. Temporarily mark the cell as used (e.g. '#') so you don’t loop; restore after recursion—this is backtracking on a word-shaped path.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Start | For each cell, try if board[i][j]==word[0] |
| 2. Match | If index == word length, success |
| 3. Explore | For each neighbor, match next char |
| 4. Mark | Flip cell to block revisits on this branch |
| 5. Recurse | Increment index |
| 6. Unmark | Restore letter for other paths |
5. Dry Run Example
Word "AB", grid row ["A","B"]: start at A, go right to B, done. If path wrong, unmark and try another start cell.
6. Key Properties
| Property | Value |
|---|---|
| Branching | Up to 4 per step |
| Depth | len(word) |
| Pruning | Mismatch stops immediately |
7. Where It Is Used
| Domain | Use |
|---|---|
| Word games | Boggle-style validation |
| Interviews | Very common grid + string pattern |
| Bioinformatics | Motif search on grids (variants) |
8. Interview Tips
Clarify reuse rules and case sensitivity; implement clean DFS with mark/unmark; mention Trie + backtracking for many words (advanced).
9. Comparison with Other Approaches
| Approach | Notes |
|---|---|
| DFS backtracking | Standard for single word |
| BFS | Possible but less natural for path-as-string |
| Trie batch | Optimize multiple queries |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(N·M·4^L) rough bound, L = word length |
| Space | O(L) recursion depth |
Implementation Example (PYTHON)
def exist(board: list[list[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
w = list(word)
def dfs(r: int, c: int, k: int) -> bool:
if k == len(w):
return True
if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != w[k]:
return False
t, board[r][c] = board[r][c], '#'
ok = (
dfs(r + 1, c, k + 1)
or dfs(r - 1, c, k + 1)
or dfs(r, c + 1, k + 1)
or dfs(r, c - 1, k + 1)
)
board[r][c] = t
return ok
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))