BacktrackingRecursion & Backtracking

Word Search

Check whether a word can be traced through adjacent grid cells without reuse, by DFS from every matching start cell with in-place visited marking.

Learn Word Search (Grid DFS) →
A
B
C
E
S
F
C
S
A
D
E
E
word
A B C C E D
1/12Search for "ABCCED": start a DFS from every cell whose letter matches 'A'.
Cell being checkedMatched prefixMismatch
PseudocodeLearn Word Search (Grid DFS) →
1for each cell (r, c): if dfs(r, c, 0): return true
2dfs(r, c, i):
3  if out of bounds or used or grid[r][c] != word[i]: return false
4  if i == len(word) - 1: return true
5  used[r][c] = true
6  found = any(dfs(neighbor, i + 1))
7  used[r][c] = false; return found   // backtrack
Variables
wordABCCED
Complexity
worst O(R · C · 3^L)
space O(L)
Speed