Return true if the word can be spelled by walking through adjacent cells of the grid — up, down, left or right. A cell cannot be used twice in the same word.
board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]]word = "ABCCED" → trueword = "SEE" → trueword = "ABCB" → false (the B would have to be reused)
No extra memory, and the check "is this cell used" becomes the same comparison as "does this letter match" — a used cell holds #, which never equals a word character.
Think of this like exploring a maze and dropping a heavy sandbag (#) on the tile you are currently standing on before taking your next step. If you wander in a circle and see a sandbag, you immediately know you've already been there on this exact trip. If you hit a dead end and need to back up, you pick up the sandbag as you step backwards, leaving the tile clean for a completely different path to explore later.
The restore is the backtracking step, and it is exactly the path.pop() of the list problems, applied to a grid.
class Solution: def exist(self, board: List[List[str]], word: str) -> bool: rows, cols = len(board), len(board[0]) # (1) def dfs(r: int, c: int, k: int) -> bool: # (2) if k == len(word): # (3) return True # matched everything if r < 0 or r >= rows or c < 0 or c >= cols: # (4) return False # off the grid if board[r][c] != word[k]: # (5) return False # wrong letter, or already used letter = board[r][c] # (6) board[r][c] = '#' # (7) mark visited found = (dfs(r + 1, c, k + 1) or # (8) dfs(r - 1, c, k + 1) or dfs(r, c + 1, k + 1) or dfs(r, c - 1, k + 1)) board[r][c] = letter # (9) undo return found # (10) for r in range(rows): # (11) for c in range(cols): if dfs(r, c, 0): return True return False
ts
function exist(board: string[][], word: string): boolean { const rows = board.length, cols = board[0].length; // (1) function dfs(r: number, c: number, k: number): boolean { // (2) if (k === word.length) return true; // (3) if (r < 0 || r >= rows || c < 0 || c >= cols) return false; // (4) if (board[r][c] !== word[k]) return false; // (5) const letter = board[r][c]; // (6) board[r][c] = '#'; // (7) const found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) // (8) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1); board[r][c] = letter; // (9) return found; // (10) } for (let r = 0; r < rows; r++) // (11) for (let c = 0; c < cols; c++) if (dfs(r, c, 0)) return true; return false;}
(2) dfs(r, c, k) asks: "starting at cell (r, c), can I spell the rest of the word, from letter k onward?"
(3) Every letter has been matched, so the word exists. This check comes first, before the edge check. The last letter may have been matched on the board's edge, and the next call would then be off the board, but the word is already complete.
(4) Off the board, so this path fails.
(5) Wrong letter, or a cell already used on this path. A used cell holds #, which never equals a real letter, so one comparison catches both.
(6) Save this cell's letter before overwriting it.
(7) Mark the cell as used by writing # into it. The same cell may not be used twice in one word.
(8) Try all four neighbours for the next letter.or stops at the first one that succeeds. The answer is stored in found rather than returned straight away, so that line (9) always runs.
(9) Put the letter back. This undo must happen whether or not the word was found. Otherwise the board is left damaged for later searches.
(10) Report whether any direction worked.
(11) Try every cell as the starting point.
Four details.
Check k == len(word) before the bounds check. The word may end exactly as the walk reaches the grid edge; testing bounds first would reject a valid match.
board[r][c] != word[k] catches two failures at once — a wrong letter and a cell already on this path, since a used cell holds #.
Save the letter in a local before overwriting. By the time you restore it, the board no longer holds it.
or short-circuits, so as soon as one direction succeeds the rest are skipped — and the restore still runs, because it is after the assignment rather than inside a return.
Writing return dfs(...) or dfs(...) or ... directly would skip the restore entirely and leave the board corrupted for the next starting cell. Assigning to found and restoring before returning is what makes it correct, and it is the most common bug in this problem.
O(\text{cells} \times 4 \times 3^{L-1}) where L is the word length. From the first cell there are 4 directions; after that only 3, because you never step back onto the cell you came from.
In practice it is far less, because a wrong letter kills a branch immediately.
O(L) space for the recursion, and O(1) extra beyond that thanks to marking the board in place.
Let's break this down:
Time Complexity: We initiate a DFS from every single cell, so there are M \times N starting points. For each DFS, the maximum depth is L (the length of the word). At the first step, we have 4 choices. For the remaining L-1 steps, we have at most 3 choices (because we can't go backwards to the cell we just left). This gives an upper bound of O(M \cdot N \cdot 4 \cdot 3^{L-1}). In reality, most paths die on the first or second step due to mismatched letters.
Space Complexity: The only extra space is the recursive call stack. The recursion goes exactly L levels deep before stopping or finding the word, which takes O(L) space. Modifying the board in-place saves us an O(M \times N) visited matrix.
Count the letters first. If the board does not contain enough of some letter in the word, return false without searching at all.
Search from the rarer end. If the word's last letter appears less often on the board than its first, reverse the word before searching. Fewer starting cells means less work. This is a genuinely clever one to volunteer.
Neither changes the asymptotic bound; both change the constant substantially on adversarial inputs.
Word Search II — many words at once, using a trie so that one walk of the grid explores all of them. 4.15.3. Running this problem once per word is too slow, and the trie is what fixes that.
Number of Islands — grid DFS without backtracking. Cells are marked visited and never restored, because you are counting regions rather than finding paths. 4.20.
That contrast is the thing to take away. Both walk a grid with DFS. Whether you undo the visited mark depends on the question:
Finding a path — undo, because a cell blocked for this path must be free for another.
Finding or counting regions — do not undo, because a cell belongs to exactly one region and revisiting it is pure waste.
Getting that backwards is the most common grid-search mistake, in both directions.
"How do you track visited cells?" Mark the board itself, and restore on the way out.
"Why restore?" A cell used by one path must be available to a different path.
"Why is it 3^{L-1} and not 4^L?" You never step back the way you came.
"What if you had many words?" Build a trie and walk the grid once — Word Search II.
"How is this different from Number of Islands?" Paths undo the mark; regions do not.
One thing to volunteer: mention searching from the rarer end of the word. It is a small, real optimisation that shows you thought about the input rather than only the algorithm.