Grid DFS with undo

39 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A 3×4 board of letters, and the word SEE. Does the word appear as a path of neighbouring cells, stepping up, down, left or right, never reusing a cell? By hand you look for an S, then look around it for an E, then around that E for another E that is not the one you just used. If a route dies you go back to the S and try another direction.

That is the whole algorithm, and the hard part is the bookkeeping: remembering which cells the current route has used so you do not step back onto them, and forgetting them correctly when you abandon the route. Done by hand with a pencil, you would mark cells and then rub the marks out.

Build the structure, one piece at a time

Piece one: the board itself, a grid you can read by row and column.

Piece two: a depth, how many letters of the word have matched so far along the current route.

Piece three: marks. Instead of a separate visited grid, overwrite the current cell with a placeholder such as # while exploring from it, and write the letter back when you return. The marked cells are exactly the current route, the pencil marks from the by-hand version.

Piece four, the rule, search(row, col, depth): if the cell is off the board, marked, or its letter is not word[depth], fail. If depth is the last letter, succeed. Otherwise mark the cell, try the four neighbours with depth + 1, unmark, and report whether any neighbour succeeded. Run search from every cell as a starting point.

Why it is correct

The invariant: the marked cells are exactly the cells on the current route. Marking happens when a cell joins the route and unmarking when the route backs off it, in stack order, so a mark never outlives its route. Because of the invariant, a cell is never used twice in one word, which is the problem's rule, and because marks are removed on return, a cell that failed on one route is free to be used by a later route that reaches it differently. Every route of length equal to the word is examined in the worst case, so a word that exists is found.

Why it is fast

From a start cell, the first step has up to 4 directions and every later step at most 3 (you cannot step back onto the cell you came from, it is marked). For a word of length L on an m×n board:

work ≤ m·n · 4 · 3^L−1, usually written O(m·n · 4^L)

The letter check at each step kills most branches immediately, which is why it runs fast in practice; the marking costs nothing extra because it reuses the board.

How to recognise it in an interview

Cues: "path in a grid", "adjacent cells", "each cell used at most once", "does the word exist", "visit every empty cell exactly once". The first thing to say: "DFS from each cell, mark on entry, unmark on return." Word Search is the example above. Word Search II has many words; build a trie of them and walk the trie alongside the board so one DFS finds all words at once. Unique Paths III is the same mark-and-unmark walk counting routes that cover every open cell.

02The idea in one line

Mark the cell, explore four ways, unmark on return.

Reach for it when: Word search, word search II (with trie), unique paths III, N-queens-style boards.

Cost: O(mn · 4^L) time.

03The walk-through, step by step

The video works one example: Word Search for 'SEE' in a 3×4 board. These are its captions in order, so you can follow without the video or check a step you missed.

1. Mark a cell, explore 4 neighbours, unmark on the way back
2. (1,0) = 'S' matches 'S': mark it, depth 1
3. (1,1) = 'F' ≠ 'E': dead end
4. (2,0) = 'A' ≠ 'E': dead end
5. (0,0) = 'A' ≠ 'E': dead end
6. No way on from (1,0): unmark it and back up
7. (1,3) = 'S' matches 'S': mark it, depth 1
8. (2,3) = 'E' matches 'E': mark it, depth 2
9. (2,2) = 'E' matches 'E': mark it, depth 3
10. Last letter matched: found 'SEE'
11. Each start cell tries 4^L paths at worst: O(m·n·4^L)

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Backtracking: Subsets (include / exclude), Permutations with a used set, Combination sum with a start index, Constraint placement with pruning, Generate valid sequences.