Word Search

Given an m x n board of letters and a word, return true if the word exists in the grid by sequentially adjacent cells (up/down/left/right). A cell may be used at most once.

Why this is worth learning

The same board cell may participate in different candidate paths, but not twice in one path. Visited state therefore belongs to one recursive branch and must be restored even when that branch succeeds.

Before coding: one-minute experiment

Can a 1x2 board [A,B] form ABA? Why must the successful return path also restore its temporary marks?

Function signature

func Exist(board [][]byte, word string) bool

Inputs / outputs

• board: grid of letters.
• word: target word.
• Return: true if the word can be formed.

Example

board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "ABCCED"
Output: true

Constraints

• 1 <= m, n <= 6
• 1 <= len(word) <= 15
• The board is rectangular; board cells and word bytes are English letters A–Z or a–z. Matching is case-sensitive.
• The board must be restored before return.

Core idea (near-solution)

Trying every start and every orthogonal walk is a complete baseline, but a matching byte is not enough: the next cell must also be unused on this particular path. For board [A,B], the walk A→B→A spells ABA only by reusing a cell, so it is invalid. Shared visited state must be undone between alternatives; a global visited set would instead discard paths that are allowed to borrow the same cell at different times.

Use DFS backtracking from each cell that matches the first letter. Mark cells as visited during a path, then unmark when backtracking.

Invariant: the current path matches the first k letters of the word without reusing cells.

Algorithm (step-by-step)

1. Start dfs(r,c,0) at each board cell; return true if one starting branch succeeds.
2. A DFS call has an in-bounds cell and current word index i. If board[r][c] != word[i], return false. A temporary # mark also fails this comparison because inputs contain letters only.
3. If i==len(word)-1, the final byte matched: return true without marking this final cell.
4. Save the current byte, then mark the cell #. Try each in-bounds orthogonal neighbor with index i+1.
5. Restore the saved byte before returning, whether a neighbor succeeded or all neighbors failed. An early success still owes this restoration.
6. If every starting branch fails, return false. Use a fresh path’s visited state for each branch; failed (r,c,i) results cannot be reused without accounting for visited cells.

Correctness sketch

At a matching cell for word position i, the cells marked by earlier calls are exactly the already-used prefix path. Rejecting mismatched or marked cells ensures the next chosen cell extends that path by one unused adjacent location. Reaching the final matching character proves a complete legal path. Trying all four neighbors covers every possible extension, and trying every start cell covers every possible first location. Restoring the board on both successful and unsuccessful returns prevents a completed branch from removing possibilities elsewhere and guarantees the caller sees the original board.

Trace (hand walkthrough)

Example input:
board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "ABCCED"
Output: true

Walk:
- path for "ABCCED": A(0,0)->B(0,1)->C(0,2)->C(1,2)->E(2,2)->D(2,1)
- all moves are adjacent and no cell reused -> true

Pitfalls to avoid

• Not unmarking a cell on backtrack.
• Reusing a cell in the same path.

Debugging lens

Compare the entire board before and after both successful and failing queries. The temporary # marker must be outside the letter alphabet. Empty words are outside the stated positive-length contract.

Complexity

For word length L, a loose bound is O(m n 4*3^(L-1)): after the first step a path cannot immediately return to its previous cell, and visited cells prune further. O(m n 4^L) is also a valid looser bound. Recursion depth is O(min(L,m n)), and the board is restored.

Implementation notes (Go)

• Mark a cell as visited by temporarily changing its value.
• Restore the cell after recursion to allow other paths.

Reconstruction checkpoint

Can a 1x2 board [A,B] form ABA? Why must the successful return path also restore its temporary marks?

Return to Backtracking · Module quiz