LeetCode 79 · Backtracking · concepts: backtracking, matrix-traversal
Problem
Given a character board and a word, return true if the word can be formed along a path of adjacent cells, each cell used at most once.
board = [["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]], word = "ABCCED" -> true
Approach — DFS backtracking on the grid (optimal)
From each cell, DFS matching the word character by character. Mark a used cell temporarily, recurse into its four neighbors, then restore it on the way back so other paths can reuse it.
def exist(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word):
return True # matched all characters
if (r < 0 or r >= rows or c < 0 or c >= cols
or board[r][c] != word[i]):
return False
board[r][c] = "#" # mark visited (avoid reuse)
found = (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))
board[r][c] = word[i] # restore (backtrack)
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return FalseTime O(rows · cols · 4^L), space O(L) recursion (L = word length).
Marking in place instead of a visited set
Overwriting board[r][c] = "#" during the recursion and restoring it after is the backtracking way to enforce “each cell once” without a separate visited structure — the undo step is what makes the same cell available to other branches. Forgetting to restore breaks all sibling paths.
Key insight
Path search on a grid with no-reuse → DFS + in-place mark/undo. It fuses grid DFS with backtracking’s choose/undo; the temporary marking is the reusable trick (and the seed of Word Search II’s trie-guided version).
Related
- concepts: backtracking, matrix-traversal
- leads to: Word Search II
- prev: Combination Sum II · next: Palindrome Partitioning
Software engineering
Infrastructure & security
Computer science
Hardware & engineering