Problem Statement

Word Search

You are given a grid of letters (m rows by n columns) and a word. Return true if you can spell the word by walking from cell to cell. Each step you take must move to a cell right next to the current one, up, down, left, or right (not diagonally). You cannot reuse the same cell twice in one path. Think of it like a word puzzle where you trace a path with your finger, and your finger is never allowed to land on the same square it already touched.

hardArrayBacktrackingMatrixBacktrackingTime: O(m * n * 4^L) · Space: O(L)

Signals to notice

find word in gridadjacent cellsexplore all paths

Brute force first

No simpler alternative — you must explore paths. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

Backtracking DFS from each cell matching the first letter. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word="ABCCED"`

Outer loop starts at (0,0). dfs(0,0,0): board[0][0]='A'==word[0]='A' -> mark (0,0)='#', recurse
dfs neighbor (0,1),k=1: 'B'==word[1]='B' -> mark (0,1)='#', recurse
dfs neighbor (0,2),k=2: 'C'==word[2]='C' -> mark (0,2)='#', recurse
From (0,2) try down (1,2),k=3: 'C'==word[3]='C' -> mark (1,2)='#', recurse
From (1,2) try down (2,2),k=4: 'E'==word[4]='E' -> mark (2,2)='#', recurse
From (2,2) try left (2,1),k=5: 'D'==word[5]='D' -> mark (2,1)='#', recurse with k=6
dfs(...,k=6): k==len(word)=6 -> return true; unwinds all true
Answer: true

What must stay true

Mark cells as visited during exploration, unmark when backtracking. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

function dfs(i, j, k):
  if k == len(word): return true
  if out-of-bounds or board[i][j] != word[k]: return false
  mark board[i][j] = '#'                       # visited
  found = dfs(i±1,j,k+1) or dfs(i,j±1,k+1)      # 4 neighbors
  board[i][j] = original                        # unmark on backtrack
  return found
# outer: for each cell, if dfs(i,j,0) return true

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not unvisiting cells after backtracking — you'll miss valid paths that reuse cells in different branches. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Backtracking Pattern