Word Search — Backtracking on a Grid
Perform DFS from each cell, marking visited cells temporarily to avoid reuse within the same path.
Problem Statement
Given a 2D board and a word, determine if the word exists in the grid using adjacent (up/down/left/right) cells without reusing a single cell twice in the same path.
Why This Problem Matters
- Introduces backtracking on matrices with visited state.
- Foundation for advanced word search and trie problems.
- Tests ability to combine recursion with board boundary checks.
Thought Process
Start DFS from matching letters
Only start exploring paths from cells that match the first character.
Mark visited cells
Temporarily mutate the board or track a visited matrix to prevent cycles within the same path.
Backtrack cleanly
Restore the cell after exploring; otherwise other paths cannot use it.
Step-by-Step Reasoning
- Loop through each cell; call dfs if board[r][c] matches word[0].
- DFS checks boundaries, character match, and base case index == word length.
- Mark cell as visited, explore four directions with index + 1, then restore cell.
- Return true when path covers entire word.
Dry Run
board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = "ABCCED"
Path found starting at (0,0).
word = "ABCB"
No valid path; DFS exhausts possibilities and returns false.
Complexity Analysis
Time
O(m·n·4^L)
Space
O(L)
Why
At most four branching choices per character with recursion depth L.
Annotated Solution
public class WordSearch {
private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
public boolean exist(char[][] board, String word) {
int rows = board.length;
int cols = board[0].length;
for (int r = 0; r < rows; r += 1) {
for (int c = 0; c < cols; c += 1) {
if (dfs(board, word, 0, r, c)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int index, int r, int c) {
if (index == word.length()) {
return true;
}
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != word.charAt(index)) {
return false;
}
char saved = board[r][c];
board[r][c] = '#';
for (int[] dir : DIRS) {
if (dfs(board, word, index + 1, r + dir[0], c + dir[1])) {
board[r][c] = saved;
return true;
}
}
board[r][c] = saved;
return false;
}
}The DFS marks each cell as visited by replacing its value temporarily; restoration enables other search paths.
Common Pitfalls
- Not restoring board cell after recursion blocks other paths.
- Allowing reuse of the same cell within a path violates problem constraints.
- Missing early exit once result is found wastes work.
Follow-Up Questions
- How would you search for multiple words simultaneously? (See Word Search II with trie.)
- Can you use bitmasking to track visited cells for small boards?