You are given a grid of letters and a word. When do you stop searching, and what stops you revisiting the same cell?
You stop on four conditions and the success check has to come first, before bounds or character comparison. Revisiting is prevented per path rather than globally: a cell is marked when the search enters it and unmarked when the search leaves it, because a cell that ruins one candidate path has to remain available to a different one.
6 min readUpdated 2026-08-15
0
Answer
Short answer
Solve word search with depth-first backtracking from each matching starting cell. Stop when the word index reaches the word length, reject out-of-bounds or mismatched cells, and mark a cell only for the current path. Restore the mark on exit so another candidate path can reuse that cell.
Was this answer helpful?
Likely follow-ups
→Now match a thousand words against the same grid. What replaces one call per word, and what does it save?
→Diagonal moves are allowed as well. Which part of your complexity argument changes?
→The grid is a hundred thousand by a hundred thousand and held on disk. What is the first thing you change?
→Prove to me that marking in place and restoring on exit leaves the grid identical to how you received it.
The two things being asked about are the two halves of every backtracking search, and candidates reliably get the first right and the second wrong. When to stop is the base case. What prevents revisiting is the state that has to be undone.
The grid is a graph whose nodes are cells and whose edges join cells sharing a side. What you are looking for is a walk through it that spells the word and never steps on the same cell twice. Saying that out loud is worth a sentence, because it explains the shape of everything that follows.
Four stop conditions, in this order
Success first: if the index into the word has reached its length, every character has been matched and you return true. This has to be tested before anything else. Test bounds or characters first and you require a further cell to exist beyond the end of the word, so a word that finishes in the bottom-right corner fails.
Then the three failures. Out of bounds. The cell's letter does not match the character at the current index. The cell is already on the path you are standing on.
privatebooleansearch(char[][] grid, String word, int r, int c, int i) {
if (i == word.length()) returntrue; // success before bounds - a match may end at an edgeif (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) returnfalse;
if (grid[r][c] != word.charAt(i)) returnfalse; // also rejects a cell marked as in-usecharletter= grid[r][c];
grid[r][c] = '#'; // in use, for this path onlybooleanfound= search(grid, word, r + 1, c, i + 1)
|| search(grid, word, r - 1, c, i + 1)
|| search(grid, word, r, c + 1, i + 1)
|| search(grid, word, r, c - 1, i + 1);
grid[r][c] = letter; // restore on BOTH outcomes - this is the backtrackreturn found;
}
Marking with a character that cannot appear in the word folds the fourth condition into the third: a marked cell fails the letter comparison, so no separate visited check is needed. That only holds if the sentinel is genuinely outside the alphabet of the word, which is an assumption to state rather than assume.
Why a global visited set is wrong, with an input that proves it
The most common defect is a visited grid that is set and never cleared, or cleared only when the whole search fails. It is wrong for a reason worth naming. Exclusion belongs to the current path, not to the search as a whole.
Take this grid, with the word AAB.
A A
B X
The word is present: start at the top-right A, move left to the top-left A, move down to B. Now watch a depth-first search that scans for starting cells in row order and marks globally.
It starts at the top-left A and matches index zero. Looking for the second A it tries the cell below first, which holds B and does not match, then moves right to the top-right A and matches index one. Looking for B from there it finds only the out-of-bounds edges, the X below, and the cell it came from. Dead end. It retreats, exhausts the remaining directions, and the attempt from that starting cell fails.
With per-path marking, both cells are released and the second attempt from the top-right A succeeds. With a global set, the top-left A is still marked, so the successful path cannot use it, and the function returns false on a grid that contains the word.
That is the whole argument. It is worth having a two-by-two example ready, because "you have to restore the state" is a claim and this is a demonstration.
Restoration also has to happen on success. Returning early out of the middle of the recursion without unmarking leaves a trail of sentinel characters through the caller's grid, and the bug shows up only in whatever runs next.
Loading diagram…
The edge that matters is the one from the recursion into the unmark, because it is taken whether the neighbours succeeded or failed. A version that only unmarks on failure passes small tests and corrupts the grid.
The bound, and why it is not the algorithm's fault
The first cell offers four directions. Every cell after it offers three, because one of its four neighbours is the cell it came from and is already on the path. So for a word of length L the search from a single starting cell explores at most four times three to the power of L minus two branches, which is the same order as three to the power of L. Multiply by the m times n possible starting cells.
Extra space is the recursion depth, which is O(L), if you mark in place. A separate visited grid costs O(m times n) instead.
The exponential is not laziness. The constraint that no cell repeats is what forbids the usual escape, which would be to memoise on the pair of cell and word index. That memo is invalid here, because whether a cell can complete the rest of the word depends on which cells the path already consumed, and a state that includes the set of consumed cells is exponential in the grid size. Being able to say why memoisation does not apply is a stronger signal than the bound itself, because it is the thing candidates try when asked to improve it.
Pruning, priced, and offered second
Once a correct solution exists, two cheap prunes are worth mentioning, and the order matters: an interviewer reads pruning offered before correctness as avoidance.
Count the letters in the grid in one pass. If the word needs more copies of some letter than the grid holds, no path can exist and you return false in O(m times n plus L) without a single recursive call. This is what makes an impossible long word fast rather than catastrophic.
Then compare the grid frequency of the word's first letter against its last. Searching a word backwards is the same problem, and starting from whichever end is rarer cuts the number of starting cells. If the first letter appears five hundred times and the last twice, reversing the word removes four hundred and ninety-eight starting cells, which is a factor of two hundred and fifty on the outer loop for the cost of reversing a string.
The follow-up direction, when the same grid is matched against many words, is a trie over the whole word set traversed alongside the grid walk. It replaces one search per word with one search that carries a trie node, so shared prefixes are explored once instead of once per word, and the walk can abandon a branch the moment the accumulated prefix leaves the trie.
The mutation you are performing on someone else's data
Marking in place is elegant. It also modifies the caller's argument. If the caller reuses the grid, or holds it concurrently, or expects it to be immutable, the function is defective even though it restores everything before returning, because during the call the grid is transiently wrong. Two threads on one grid corrupt each other.
Raising that unprompted converts a puzzle answer into an engineering one. The alternatives are a separate boolean grid at O(m times n) space, or a set of coordinates on the path at O(L) space with a hash lookup per step, and which you choose depends on whether the grid is yours to write to.
The stopping conditions are ordered so success is checked first, and the marking is scoped to one path, because a cell that killed one candidate route has done nothing to disqualify itself from another.