TL;DR
DFS backtracking with per-character pruning and in-place cell marking — O(m·n · 3^L) time (L = len(word)), O(L) space.
Approach 1 — Brute force: enumerate full paths, compare at the end
The naive idea: from every cell, enumerate every simple path of exactly len(word) steps (carrying a visited set and the string built so far), and only when a path reaches full length compare it against word.
def exist(board: list[list[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
def paths(r: int, c: int, used: set[tuple[int, int]], acc: str) -> bool:
acc += board[r][c]
if len(acc) == len(word):
return acc == word # only compare once the path is complete
used = used | {(r, c)} # copies the set at every step
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in used:
if paths(nr, nc, used, acc):
return True
return False
return any(
paths(r, c, set(), "")
for r in range(rows)
for c in range(cols)
)
Complexity: O(m·n · 3^L · L) time (every length-L path is walked and its string rebuilt, mismatch or not), O(L²) space from copying used and acc per level.
This explores the entire 3^L-branching tree even when the first character is wrong. With L = 15 that is a huge number of wasted paths per starting cell.
Approach 2 — Backtracking with early mismatch pruning and in-place marking
Key idea: compare character by character as you walk. As soon as board[r][c] != word[i], prune that branch — nothing below it can spell the word. This is standard backtracking: extend a partial solution one choice at a time, and undo the choice when the branch fails. For the “used” bookkeeping, temporarily overwrite the cell with "#" (which matches no letter) and restore it on the way out, so the board itself becomes the visited set.
def exist(board: list[list[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
def dfs(r: int, c: int, i: int) -> bool:
if board[r][c] != word[i]:
return False # prune: mismatch kills the branch
if i == len(word) - 1:
return True # matched the last character
saved = board[r][c]
board[r][c] = "#" # mark in place
found = False
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
found = True
break
board[r][c] = saved # unmark (backtrack)
return found
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))
Walkthrough on the example board with word = "SEE":
A B C E
S F C S
A D E E
- Starts at (0,0)
A, (0,1) B, (0,2) C, (0,3) E all fail instantly: first char must be S — one comparison each, no descent.
- (1,0)
S matches word[0]. Mark it #. Neighbors: (2,0) A, (0,0) A, (1,1) F — none is E; every child dies at depth 1. Restore S.
- Continue scanning; (1,3)
S matches. Mark #. Try (2,3) E = word[1]: mark #, try its neighbors for word[2] = "E": (1,3) is # (in use — sentinel can’t match), (2,2) is E → i == 2 == len(word)-1 → True bubbles all the way up.
The successful descent from (1,3):
flowchart TD
A["(1,3) S == word[0], mark #"]
A --> B["(2,3) E == word[1], mark #"]
B --> C["(1,3) is #, in use, skip"]
B --> D["(2,2) E == word[2], i == len-1 → True"]
Complexity: O(m·n · 3^L) time — from each of m·n starts, each path step has at most 3 unvisited directions (you never go back where you came from); O(L) recursion stack. No extra visited structure.
Approach 3 — Add feasibility pruning: letter counts + rarer-end start
Key idea: two cheap global checks cut the worst cases. (1) If word needs more copies of some letter than the whole board contains, answer False without searching. (2) The search is cheapest when the first character is rare on the board — if the last character of word is rarer than the first, search for the reversed word instead (a path spelling the reverse exists iff one spelling the word does, walked backward).
from collections import Counter
def exist(board: list[list[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
board_count = Counter(ch for row in board for ch in row)
word_count = Counter(word)
if any(word_count[ch] > board_count[ch] for ch in word_count):
return False # board can't even supply the letters
if board_count[word[0]] > board_count[word[-1]]:
word = word[::-1] # anchor the search on the rarer end
def dfs(r: int, c: int, i: int) -> bool:
if board[r][c] != word[i]:
return False
if i == len(word) - 1:
return True
saved = board[r][c]
board[r][c] = "#"
found = False
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
found = True
break
board[r][c] = saved
return found
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))
Walkthrough with word = "ABCB": the board contains exactly one B, but word needs two → the Counter check returns False immediately, zero DFS calls. (Approach 2 would have explored the A → B → C prefix before failing.)
Complexity: same worst-case O(m·n · 3^L) time and O(L) space, but the pre-checks are O(m·n + L) and routinely turn pathological inputs (e.g. a board of all As and word = "AAAAAAAAAAAAAAB") into instant rejections or far shallower searches.
Common pitfalls
- Forgetting to restore the cell after recursion — including on the success path if you return early before unmarking; corrupted boards break sibling starting positions.
- Using a shared visited set without removing entries on backtrack — cells stay “used” for unrelated branches and valid paths get missed.
- Checking
i == len(word) after moving instead of i == len(word) - 1 at the match — both can work, but mixing the two conventions yields off-by-one misses on single-character words.
- Allowing diagonal moves or revisits — the path is 4-directional and simple;
[["a"]] with word = "aa" must return False.
Pattern takeaway
Grid-path backtracking = DFS + fail fast + undoable state. Check the constraint (character match) before recursing so mismatched subtrees are never entered, encode “visited” by mutating the structure itself with a sentinel and restoring it on unwind, and when the search has a choice of anchor, anchor it on the rarest element. The same skeleton solves island counting, path finding with restrictions, and any exists-a-path puzzle on a grid.