Compile Ready
Module 6 · Board Search

Word Search

MediumProblem 12 of 17 8 min read ~20 min to solve LeetCode
BacktrackingDFSMatrixRecursionPruningIn-place Marking
Asked atAmazonGoogleMicrosoftMetaBloomberg

Problem Statement

Given an m x n board of characters and a string word, return whether word exists in the grid. The word must be formed by sequentially adjacent cells, where adjacent means horizontally or vertically neighboring. The same board cell may not be used more than once in a single word path.

Input

A character grid board and a target string word.

Output

A boolean: true if some valid path spells the whole word, otherwise false.

Constraints

  • •1 <= m, n <= 6
  • •1 <= word.length <= 15
  • •board and word consist of lowercase and uppercase English letters
  • •The same cell cannot be reused within one path

Examples

Example 1

Input: 
board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = ABCCED
Output: true
Explanation: A valid path is **A** at row 0 column 0, **B** at row 0 column 1, **C** at row 0 column 2, **C** at row 1 column 2, **E** at row 2 column 2, and **D** at row 2 column 1.

Example 2

Input: 
board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = SEE
Output: true
Explanation: Starting at **S** in row 1 column 3, move down to **E** and then left to another **E**.

Example 3

Input: 
board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = ABCB
Output: false
Explanation: The only obvious prefix **ABC** would need to reuse the **B** cell, which is not allowed.

Learning Objectives

  • Recognise grid word search as board backtracking with a moving cell and a word index.
  • Mark a cell as visited before exploring neighbors and restore it afterward.
  • Prune immediately on bounds, character mismatch, or revisiting the current path.
  • Use a returned boolean to stop the search as soon as one complete path is found.

Intuition

Pattern Recognition

This is a board-search backtracking problem: build one path through a grid while obeying local constraints. The state is the current cell and the next index of word to match. The choices are the four neighboring cells. The base case is matching every character.

The place, validate, recurse, undo pattern appears as a visited marker. Once a cell matches word[index], mark that cell so the same path cannot use it again, recurse into four directions for index + 1, then restore the original character before returning. The in-place trick uses a plain placeholder character such as # instead of a separate visited matrix; because the cell is restored, sibling branches see the board exactly as it was.

This is a single-solution search, not an enumeration problem. Returning true from the DFS lets the first completed word path short-circuit all remaining branches.

Common mistakes

  • ×Forgetting to restore the marked cell, which corrupts sibling searches from other starting cells.
  • ×Allowing diagonal moves even though the problem only permits horizontal and vertical adjacency.
  • ×Checking visited after overwriting the cell in a way that loses the original character.
  • ×Continuing to explore after the word is already matched instead of returning **true** immediately.

Algorithm Explanation

State

Each DFS frame carries row, col, and index. The board itself stores the current path by temporarily replacing visited cells with #. A frame is valid only when the position is inside the board and board[row][col] equals word[index].

Recursion tree

For word = ABCCED, the search tries each board cell as a possible starting A. From the A at row 0 column 0, the next level branches to up, down, left, and right for B. Three branches are cut by bounds or mismatch, while the right branch reaches B. The same pattern repeats: from B, only the right C survives; from that C, the downward C survives; then E and D complete the word.

Pruning

Cut a branch if the cell is out of bounds, if the board character does not match the current word character, or if the cell is already marked # by the current path. The character mismatch check is the main pruning. The returned boolean also prunes the rest of the search once a full word is found.

Algorithm

  1. Iterate over every cell as a possible start for word[0].
  2. In DFS, return true when index == word.length.
  3. Reject the frame if the cell is outside the board or does not match word[index].
  4. Save the original character and place the visited marker # in the cell.
  5. Recurse to the four neighboring cells with index + 1.
  6. Undo by restoring the saved character before returning.
  7. If any start returns true, return true; otherwise return false.

Solutions

Solution: In-place DFS with mark and restore

Treat each cell as a possible first character. The DFS validates the current character, places a temporary visited marker, explores four neighbors, and then restores the cell. This keeps auxiliary space to the recursion stack while preserving the board for other starting points.

Step-by-step

  1. Scan every row and col in the board.
  2. Call DFS from that cell with index = 0.
  3. In DFS, finish successfully when index reaches word.length.
  4. Reject out-of-bounds cells and cells whose character does not equal word[index].
  5. Save the current character, write # into the board, and recurse up, down, left, and right.
  6. Restore the saved character before returning the boolean result.
Time

O(m * n * 3^L)

Space

O(L)

There are m * n starts. After the first step, each path has at most 3 useful directions because it should not immediately return to the marked previous cell. L is word.length.

Java implementation

Loading…

Dry Run

Sample input

board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = ABCCED. Track one successful path and the pruned branches around it.

stepcellchoiceaction (place/undo)state
1(0,0)match Aplace #path A, index moves to 1
2(0,1)move right to Bplace #path A -> B
3(0,2)move right to Cplace #path A -> B -> C
4(0,3)try E for next Cprunemismatch, return to (0,2)
5(1,2)move down to Cplace #path A -> B -> C -> C
6(2,2)move down to Eplace #path A -> B -> C -> C -> E
7(2,1)move left to Dplace #word complete
8return stackfound trueundo restore cellsall markers are restored as true propagates

The placeholder prevents reusing cells already in the path. Even though the search returns true, every active frame restores its cell before unwinding, so the board is left unchanged.

Interview Tips

Lead with the invariant: every active path has unique cells because chosen cells are marked and later restored. Mention both implementation options, in-place # marking or a visited matrix, then prefer in-place marking when mutation is allowed. Also say why the boolean return matters: Word Search asks whether one path exists, so the first full match should stop the recursion.

Likely follow-ups

  • How would you return the actual path of coordinates instead of only **true** or **false**?
  • How would the solution change if diagonal moves were allowed?
  • How would you search for many words on the same board efficiently?
  • How would you handle a board where **#** could appear as a normal character?

Similar Problems

N-Queens
HardAnother board problem where marking constraints controls the search.
Sudoku Solver
HardUses the same place, validate, recurse, undo structure with richer constraints.
Palindrome Partitioning
MediumA different DFS where invalid choices are pruned before recursion.
Word Search II
HardExtends board DFS to many words using trie pruning.

Key Takeaways

  • Grid search becomes backtracking when a path cannot reuse cells.
  • Mark before exploring neighbors and restore before returning to keep sibling branches independent.
  • Bounds and character mismatch checks are powerful pruning gates.
  • Use a boolean return for existence problems so one found path stops the search.
Reusable template: Board path DFS: validate the current cell, mark it as used, recurse into allowed neighbors for the next symbol, restore the cell, and return early when a full path is found.