A word-hunt service is asked whether a target string sits on a letter raster as a 4-connected walk — no diagonals, no reused cell. The intern generated every walk of length word.length() from every cell, then compared the string at the leaf. A 3×4 fixture in staging returned. A 12×12 board with a sixteen-letter query was still enumerating paths when the request timed out.
Word Search asks whether the word is a 4-connected walk on the grid, using each cell at most once. This is an interview writeup, not a layout lecture. The graphs post owns the grid. Backtracking owns choose-recurse-undo. Here we only care about a start cell that matches word[0], four neighbor deltas, and restoring the mark so the next branch sees a free cell.
The problem
Given a char[][] board and a String word, return whether word exists on the board. Consecutive letters must sit on 4-adjacent cells — up, down, left, right, not diagonals. The same cell may not be used twice in one walk.
A B C E
S F C S
A D E E word = ABCCED → true
A B C E
S F C S
A D E E word = SEE → true
A B C E
S F C S
A D E E word = ABCB → false
A word = A → trueNote: Off-board is a miss. Bounds-check first, then the letter, then “already used.” A 4-direction int[][] dirs table is the neighbor list. This is not Unique Paths — that prompt counts right-and-down routes on an empty grid and lives under arrays. Here a cell may not be reused, the next letter is a constraint, and the answer is a boolean.
Generating every walk of that length is the honest brute force
From every cell, nest a 4-way neighbor choice until the path holds word.length() cells, then compare the string. You do not look at the letters until the walk is complete. Correct. Exponential.
boolean existEveryWalk(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char[] path = new char[word.length()];
boolean[][] used = new boolean[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (fill(board, r, c, 0, path, used, dirs, word)) {
return true;
}
}
}
return false;
}
boolean fill(char[][] board, int r, int c, int i, char[] path,
boolean[][] used, int[][] dirs, String word) {
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || used[r][c]) {
return false;
}
used[r][c] = true;
path[i] = board[r][c];
boolean hit = false;
if (i == path.length - 1) {
hit = word.equals(new String(path));
} else {
for (int[] d : dirs) {
if (fill(board, r + d[0], c + d[1], i + 1, path, used, dirs, word)) {
hit = true;
break;
}
}
}
used[r][c] = false;
return hit;
}At a 3×4 fixture this is a rounding error. On a larger board you paid every simple walk of length L: you finished the path before you asked whether the letters matched.
Start on the first letter, mark, recurse, undo
Scan row-major. A start is a cell whose letter is word[0]. From there the state is (r, c, i): you sit on a cell and you still need word[i..].
- Bounds or
board[r][c] != word[i]— return. - Last letter — return true.
- Otherwise choose: write a sentinel so this cell is used. Recurse on four neighbors at
i + 1. Undo: restore the letter before you try the next neighbor or give up.
Walk ABCCED on the first board. The mismatch ABCB dies when C has no unused neighbor B.
A B C E
S F C S
A D E E word = ABCCED
start (0,0) A
mark A
(0,1) B
mark B
(0,2) C
mark C
(1,2) C
mark C
(2,2) E
mark E
(2,1) D last letter, true
word = ABCB
start (0,0) A → B → C
neighbors of that C: E, C, B(used) — none is B
undo C, undo B, undo A
other A starts fail
→ falseThe Java is that walk. Mutation is allowed if you restore; a boolean[][] is the same mark.
boolean exist(char[][] board, String word) {
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char[] w = word.toCharArray();
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[0].length; c++) {
if (board[r][c] == w[0] && search(board, r, c, 0, w, dirs)) {
return true;
}
}
}
return false;
}
boolean search(char[][] board, int r, int c, int i, char[] w, int[][] dirs) {
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length
|| board[r][c] != w[i]) {
return false;
}
if (i == w.length - 1) {
return true;
}
char saved = board[r][c];
board[r][c] = '#';
for (int[] d : dirs) {
if (search(board, r + d[0], c + d[1], i + 1, w, dirs)) {
board[r][c] = saved;
return true;
}
}
board[r][c] = saved;
return false;
}Time is O(mn * 4^L) — up to mn starts, four neighbors per step, depth L = word.length(). After the first hop a used cell kills the reverse, so 3-way is the usual tighter sketch. Space is O(L) for the call stack (and a boolean[][] if you refuse to mutate).
Note: Undo the mark. Forget the restore and every later start inherits a board with holes. '#' is safe on an A–Z board; if the alphabet is unconstrained, use boolean[][].
What interviewers usually poke next
- Word Search II. Many words on the same board. A trie of the dictionary so one walk answers all of them. This file stays one word; that writeup lives under tries.
- Read-only board.
boolean[][] usedis the mark; still undo. Same choose-recurse-undo. - Iterative frames. An
ArrayDequeof(cell, index)plus an explicit undo. Notjava.util.Stack. NotArrayList.remove(0). - Unique Paths envy. Counting right-and-down routes is a DP table under arrays. Overlapping prefixes do not add here: reuse is forbidden and the next letter must match.
- Cheap reject. If a letter in
wordappears more times than on the board, return false before you search. Optional prune; the walk is still the answer.
You are done with this problem when you can say, out loud, why finishing every walk of length L is correct, why starting only on word[0] and pruning on a mismatch is the search, and why the undo is what lets the next neighbor see a free cell.