Word Search
Word Search is a medium recursion & backtracking problem solved with the 2d matrix backtracking pattern.
The best approach, optimal (mark in place + early pruning), runs in O(m · n · 3^L) time and O(L) space.
Below are 2 approaches in Java, from dfs with a separate visited array up.
Problem
Given an m × n grid of letters and a word, return whether the word can be traced through adjacent cells (up, down, left, right) without using any cell more than once.
Examples
Example 1
- Input
board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = "ABCCED"- Output
true
Example 2
- Input
same board, word = "ABCB"- Output
false- Why
- The B would have to be reused.
Constraints
1 <= m, n <= 6,1 <= word.length <= 15- Letters connect horizontally or vertically; a cell is used at most once per word.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| DFS with a separate visited array | O(m · n · 3^L) | O(m · n) |
| Optimal (mark in place + early pruning) | O(m · n · 3^L) | O(L) |
1DFS with a separate visited array
O(m · n · 3^L)L = word length. After the first step each cell has at most 3 unvisited directions.O(m · n)From each starting cell, DFS in four directions matching the next character, using a boolean visited grid.
- For each cell, dfs(r, c, 0).
- dfs fails on out-of-bounds, visited or mismatched cells.
- Mark visited, try four neighbours with k + 1, unmark.
class Solution {
private static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
public boolean exist(char[][] board, String word) {
boolean[][] seen = new boolean[board.length][board[0].length];
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
if (dfs(board, word, 0, r, c, seen)) return true;
return false;
}
private boolean dfs(char[][] b, String w, int k, int r, int c, boolean[][] seen) {
if (k == w.length()) return true;
if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || seen[r][c] || b[r][c] != w.charAt(k)) return false;
seen[r][c] = true;
for (int[] d : DIRS) if (dfs(b, w, k + 1, r + d[0], c + d[1], seen)) return true;
seen[r][c] = false;
return false;
}
}2Optimal (mark in place + early pruning)
O(m · n · 3^L)O(L)Recursion depth only.Mark a cell by overwriting it with '#' during the search and restoring it afterwards, which removes the visited grid. Before searching, check that the board has enough of each letter; this prunes hopeless cases.
- If the board lacks enough copies of any letter, return false.
- dfs: bounds and match check; tmp = b[r][c]; b[r][c] = '#'; recurse into 4 neighbours; restore.
class Solution {
public boolean exist(char[][] board, String word) {
int[] count = new int[128];
for (char[] row : board) for (char ch : row) count[ch]++;
for (char ch : word.toCharArray()) if (--count[ch] < 0) return false;
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
if (dfs(board, word, 0, r, c)) return true;
return false;
}
private boolean dfs(char[][] b, String w, int k, int r, int c) {
if (k == w.length()) return true;
if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != w.charAt(k)) return false;
char tmp = b[r][c];
b[r][c] = '#';
boolean found = dfs(b, w, k + 1, r + 1, c) || dfs(b, w, k + 1, r - 1, c)
|| dfs(b, w, k + 1, r, c + 1) || dfs(b, w, k + 1, r, c - 1);
b[r][c] = tmp;
return found;
}
}Edge cases to test
- Word longer than the number of cells
- Paths that revisit a cell
Hints
Hint 1
DFS from every cell that matches word[0]. Mark a cell as visited while it is on the current path and unmark it when you backtrack.
FAQ
What is the best time complexity for Word Search?
Optimal (mark in place + early pruning) runs in O(m · n · 3^L) time and O(L) extra space.
Which pattern does Word Search use?
It is a recursion & backtracking problem that uses the 2d matrix backtracking pattern.
Is there a brute force solution for Word Search?
Yes. DFS with a separate visited array takes O(m · n · 3^L) time and O(m · n) space. From each starting cell, DFS in four directions matching the next character, using a boolean visited grid.
Which edge cases should I test for Word Search?
Word longer than the number of cells; Paths that revisit a cell.