You are given a grid of letters and a word. When do you stop searching, and what stops you revisiting the same cell?

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.

The question contains both halves of backtracking

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.

private boolean search(char[][] grid, String word, int r, int c, int i) {
    if (i == word.length()) return true;                    // success before bounds - a match may end at an edge
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return false;
    if (grid[r][c] != word.charAt(i)) return false;         // also rejects a cell marked as in-use

    char letter = grid[r][c];
    grid[r][c] = '#';                                       // in use, for this path only

    boolean found = 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 backtrack
    return 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.

flowchart TD
  E[enter cell] --> C{letter matches}
  C -- no --> F[return false]
  C -- yes --> M[mark cell in use]
  M --> N[recurse into four neighbours]
  N --> U[unmark cell]
  U --> R[return whatever the neighbours found]

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.

© 2026 Preptima. Originally published at preptima.com.