Word Search
WHAT IT SAYS
Given a grid of characters and a word, decide whether the word can be spelled by walking from cell to adjacent cell, never using the same cell twice.
WHAT IT'S REALLY ASKING
"You are not searching the grid for a word — you are searching for a PATH, and a path is not allowed to step on itself. At any instant only one path is alive: the one sitting on your call stack. So how many cells actually need to be marked as 'in use', and for how long?"
Explore every path, carrying a copy of the visited grid
O(m*n*4^L) time, and an O(m*n) copy at EVERY node of the recursionFrom each starting cell, try all four directions at each step, matching characters as you go. To stop a path from reusing a cell, hand each branch its own copy of the visited grid so the branches cannot interfere with each other.
WHERE THE WORK IS WASTED — The copies are the crime, and the numbers say so. Between a node and its child, the visited state changes by exactly one cell — yet you duplicate all m*n of them, and you do it once per node of an exponential tree. Worse, the copy is storing the state of cells that have nothing to do with the path you are on: the branch that went east has no interest in the cells the branch that went west touched, because that branch is already dead and gone. You are snapshotting a global when the only thing that changed is local.
The cells in use are exactly those on the stack.
Depth-first search explores exactly one root-to-leaf path at a time. When you return from a branch, that branch is finished — nothing in it is part of any path that is still alive, and nothing in it will be looked at again by the search that continues. So 'visited' is not a global fact about the grid. It is a property of the current call stack, and the call stack is at most L frames deep. At any instant at most L cells are legitimately marked, no matter how enormous the grid is. That licenses the mutation. Mark the cell on the way IN, and unmark it on the way OUT. The lifetime of the mark then coincides exactly with the lifetime of the stack frame that owns it — which means every sibling branch sees the grid in precisely the state it would have seen if you had handed it a private copy. Mutating shared state is safe when the mutation is perfectly undone, and the recursion's structure is what guarantees the undo happens. The second half is the pruning, and it costs nothing. If the character in this cell does not match the character the word needs right now, then every path through this cell is dead — not unlikely, dead — because the word's letters are fixed. Test the character BEFORE you descend, and four entire subtrees evaporate on a single comparison. That is what keeps the exponential base near four instead of blowing up.
DFS with in-place marking
O(m*n*4^L) time worst case, O(L) extra space — the recursion stack, and nothing elseFor each cell, start a DFS carrying the index into the word. Return false immediately if you are off the grid or the character does not match; return true if you just matched the final character. Otherwise overwrite the cell with a sentinel that cannot appear in the word, recurse into the four neighbours with index+1, restore the original character on the way out, and return whether any neighbour succeeded.
Borrow and Return the State
YOU'LL SEE IT AGAIN WHEN
- The search is over paths or orderings where an element cannot be reused, and only one path is alive at any moment.
- The naive fix is to copy the shared state at every node — even though the state changed by O(1) and the copy costs O(size).
- Failure at a node is total: the mismatch kills every descendant, so the check belongs before the descent, not after it.