BacktrackingAlgorithmaka boggle search, find word in grid

Word Search (Grid DFS)

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.

▶ VisualizePattern: Depth-First SearchPractice (3)
Progress

Overview

Word Search asks whether word appears in a letter grid as a path of horizontally/vertically adjacent cells, each used at most once. The solution is Maze Search (Grid Backtracking) where the "wall" test is board[r][c] != word[k] and the target is k == len(word).

Marking visited cells in place (temporarily overwriting with #) avoids a separate visited matrix and is a standard interview trick. For many words on one board (Word Search II), replace the single word with a Trie so that all words are searched in one DFS pass, and prune trie nodes that have been fully matched.

backtrackinggridDFSstring matchingtrie

Intuition

A mental model before the formal terms.

Put a finger on every cell that matches the first letter. From there, spell the word by sliding to a neighbor that matches the next letter, never returning to a cell already under your finger trail. If you get stuck, lift your finger back one letter and try another neighbor.

The trie variant is spelling all words at once: at each cell you only continue if some word in the dictionary has the current path as a prefix.

How it works

  1. For every cell (r, c), call dfs(r, c, 0).
  2. dfs(r, c, k): if k == len(word) return true. If out of bounds or board[r][c] != word[k] return false.
  3. Save board[r][c], overwrite with #, recurse into four neighbors with k + 1, then restore the character.
  4. Return true as soon as any neighbor succeeds. Optional pre-check: if the letter counts of word exceed those of the board, return false immediately; if the last letter is rarer than the first, search the reversed word.

Why it works

The # overwrite ensures each cell is used at most once on the current path (a # never equals a letter of the word), and restoring it after the calls means sibling branches see the original board.

Depth-first exploration from every start cell is exhaustive over all simple paths whose letters spell the word; the mismatch check prunes every branch as early as the first wrong letter, so the search never explores paths that cannot become the word.

With a trie, the invariant is "the current path is a prefix of at least one unfound word"; when the invariant fails there is no point continuing, and removing found words from the trie keeps that prune tight.

Recognition

How to tell a problem wants this.

  • Letter grid + "does this word exist as a path of adjacent cells".
  • Path constraints ("no cell reused") with a string as the target — pruning on a mismatch at every step.
  • Many words over one board — that is the Trie + DFS combination.
“connected groups” → Depth-First Search“all combinations” → Backtracking“prefix” → Trie

Interactive visualization

Play, step, change the input. ← → and space work too.

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

Pseudocode

1for each cell (r, c): if dfs(r, c, 0): return true
2dfs(r, c, k):
3  if k == len(word): return true
4  if out of bounds or board[r][c] != word[k]: return false
5  saved = board[r][c]; board[r][c] = "#"
6  found = any(dfs(nr, nc, k + 1) for 4 neighbors)
7  board[r][c] = saved
8  return found

Implementations

1from collections import Counter
2 
3# Grid DFS: trace a word through orthogonally adjacent cells without reusing
4# any cell. The key trick is marking visited IN PLACE and restoring on the way
5# out, which needs no separate visited grid and no allocation per branch.
6 
7 
81 · Try every cell as a starting point
9def exist(board: list[list[str]], word: str) -> bool:
10    if not word:
11        return True
12    rows = len(board)
13    if rows == 0:
14        return False
15    cols = len(board[0])
16 
172 · Bounds and character check first, so recursion never runs on a miss
18    def dfs(r: int, c: int, k: int) -> bool:
19        if not (0 <= r < rows and 0 <= c < cols):
20            return False
21        if board[r][c] != word[k]:
22            return False
23        if k == len(word) - 1:
24            return True
25 
263 · Mark in place with a sentinel that cannot appear in the word
27        saved = board[r][c]
28        board[r][c] = "\u0000"
29 
30        found = (
31            dfs(r + 1, c, k + 1)
32            or dfs(r - 1, c, k + 1)
33            or dfs(r, c + 1, k + 1)
34            or dfs(r, c - 1, k + 1)
35        )
36 
374 · Restore on the way out — this is what makes it a search, not a walk
38        board[r][c] = saved
39        return found
40 
41    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))
42 
43 
445 · A cheap prune: if the board lacks enough of some letter, give up early
45def feasible(board: list[list[str]], word: str) -> bool:
46    have = Counter(ch for row in board for ch in row)
47    need = Counter(word)
48    return all(have[ch] >= n for ch, n in need.items())
Walkthrough
  1. 0 <= r < rows and 0 <= c < cols is the chained-comparison bounds check, which reads as the mathematical condition.
  2. dfs is a closure, so the recursive calls pass only the three changing coordinates.
  3. any(dfs(r, c, 0) for r in range(rows) for c in range(cols)) short-circuits on the first success, replacing the nested loop with one expression.
  4. The mark-and-restore is identical to the other languages; Python lists of lists are mutable, so board[r][c] = ... works directly.
  5. Counter makes feasible a two-line function, and have[ch] returns 0 for a missing key rather than raising.
Complexity (this implementation)
time O(rows * cols * 4^L) · space O(L) for the recursion

Recursion depth is the word length, so RecursionError is only a risk for words longer than about 1000 characters.

Language notes
  • collections.Counter supports have[ch] on a missing key returning 0, unlike a plain dict which raises.
  • Counter(word) - Counter(...) and <= between Counters express subset-of-multiset directly: Counter(word) <= have is the whole feasible check in one expression (3.10+).
  • Chained comparisons (0 <= r < rows) evaluate r once and are both faster and clearer than two and-joined tests.
  • A grid of strings would be immutable and could not be marked in place; a list of lists (or a bytearray per row) is required.
Common mistakes in this language
  • Passing a list of *strings* as the board, which cannot be mutated — board[r][c] = x raises TypeError.
  • Forgetting the restore.
  • Using board[r][c] != word[k] with k == len(word), which raises IndexError rather than silently reading garbage.
Language differences that matter here
  • Mutability of the grid decides the representation: Python needs a list of lists because strings are immutable, while C++ can use std::string rows and JS/TS can use arrays of single-character strings.
  • Out-of-range word indexing fails differently: Python raises IndexError, JS/TS return undefined (which compares unequal and silently returns false), and C++ std::string::operator[] at size() returns the null terminator.
  • Letter counting: Python Counter is a one-liner with a 0 default, JS/TS need a Map plus ?? 0, and C++ uses a fixed 256-entry array — the fastest of the three and the least general.
  • A closure capturing the grid is idiomatic in JS/TS and Python; C++ needs either a lambda with explicit captures or a free function taking the grid by reference, which is why the C++ version has the forward-declaration wrinkle.

Complexity

Best
—
Average
—
Worst
O(R · C · 3^L)
Space
O(L)

L = word length. Each of the R·C starts explores at most 3 new directions per step (never back into the previous cell). Word Search II with a trie of total length T is O(R · C · 3^Lmax) with O(T) trie space.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • One or a few words against a small board (≤ 15×15, L ≤ 15).
  • Many words against one board — build a Trie and run a single DFS per start cell.
Avoid it when
  • Words may reuse cells or the path is fixed (straight lines only) — then simple scanning per direction is O(R · C · 8 · L).
  • Substring search in a 1D string — use Knuth–Morris–Pratt (KMP) or Rabin–Karp.

Alternatives

Maze Search (Grid Backtracking)TrieDepth-First Search (DFS)

Common mistakes

  • Not restoring the cell after the DFS, corrupting the board for subsequent start cells.
  • Checking k == len(word) after the bounds check, which fails when the last letter sits on the grid edge.
  • Using a separate visited array but forgetting to unmark it.
  • In Word Search II, collecting a found word repeatedly — mark the trie node as found (set its word to null) after the first hit.
  • Skipping the letter-frequency pre-check and timing out on adversarial boards full of the same letter.

Interview patterns

  • Word Search I: single word, in-place marking.
  • Word Search II: trie + DFS, prune trie leaves after collection, letter-frequency pre-check.
  • Reverse the word when its last letter is rarer on the board than its first — fewer start cells.
Interview questions on this
Mock interviews

Example problems

Number of IslandsmediumWord SearchmediumWord Search IIhard