Trie-guided grid DFS

48 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 × 3 board of letters and a list of words, oath and eat. A word is found if you can trace it through adjacent cells (up, down, left, right) without reusing a cell. Which words are on the board?

By hand you would take the first word, look for its first letter on the board, and try to trace it; then take the second word and start over. That is one full board search per word. With 10,000 words and a 12 × 12 board, each word's search can branch into thousands of paths, and the board is explored 10,000 separate times, mostly along paths that no word uses.

Build the structure, one piece at a time

Two pieces. First, put all the words into one trie, a tree of letters where shared prefixes share nodes: root → o → a → t → h✓ and root → e → a → t✓. Second, walk the board with a depth-first search, but carry a trie pointer along. From a cell you may only step to a neighbour whose letter is a child of the current trie node. If there is no such child, the whole branch is dead, for every word at once.

1. Start at (0,0), letter o. The root has a child o, so enter it. Trie pointer: node o.
2. Neighbour (1,0) is e. Node o has no child e. Prune that direction without looking further.
3. Neighbour (0,1) is a. Child exists; pointer: node a under o. Then (0,2) t, then (1,2) h: that node is flagged. Found oath.
4. Unmark the cells on the way back. The oath branch can even be deleted from the trie now, since it will never match again.
5. Start at (1,0), letter e: root has child e. (1,1) a, (2,1) t, flagged: found eat.
6. Starts at cells whose letter is not a child of the root die immediately.

The trie pointer is the structure: it records "which prefix have I spelled so far", and the board walk and the trie walk move together, one letter per step.

Why it is correct

The invariant: the trie node you are standing on is exactly the prefix spelled by the path of cells behind you. Stepping to a neighbour appends one letter to the path and moves to that letter's child, so the invariant holds after the step. Pruning is safe because if the trie has no child for a letter, no word in the list continues the current prefix with that letter, so no word can be completed through that cell. Reporting a word whenever the node is flagged is complete, because every placement of every word spells a root-to-flag path, and the search tries every start cell and every direction that the trie permits.

node(path) = root ∘ s[c1] ∘ s[c2] ∘ … ; prune when child does not exist

Why it is fast

Building the trie costs the total length of all words. The search starts at each of the m × n cells and, from each, follows at most 4 directions per step for at most L steps, so the worst case is O(mn · 4^L), the same bound as searching one word. The point is that this bound is paid once for all 10,000 words instead of once per word, and in practice the trie prunes almost every branch after two or three letters, so the real work is a small fraction of the bound.

How to recognise it in an interview

Cues: many words to find in one board or one stream, "find all words", a dictionary plus a path or sequence constraint. Say: I will build a trie of the words and search the board once, guided by the trie, so dead prefixes are cut immediately. Word Search II is the example. Stream of Characters stores the words reversed in a trie and walks the last few typed characters backwards. Word Squares uses the trie to list all words with a given prefix while building the square row by row.

02The idea in one line

Build a trie of all words; walk the grid and the trie together, pruning dead branches.

Reach for it when: Word search II, stream of characters, concatenated words.

Cost: O(mn · 4^L) with heavy pruning.

03The walk-through, step by step

The video works one example: Word Search II for [oath, eat] on a 3×3 board. These are its captions in order, so you can follow without the video or check a step you missed.

1. Put every word in one trie; a cell is worth visiting only if the trie has that child
2. Start at (0,0) 'o': root has child 'o', enter it
3. Neighbour (1,0) 'e': node 'o' has no child 'e' → prune that branch
4. Neighbour (0,1) 'a': child exists, go deeper
5. (1,1) 'a': no child 'a' → prune; (0,2) 't' → go on
6. (1,2) 'h': child exists and it is a word end: found 'oath'
7. Unmark the path on the way back; the trie branch for 'oath' can be removed (no more hits)
8. Start at (1,0) 'e': root has child 'e'
9. (1,1) 'a' then (2,1) 't': both match, 't' is a word end: found 'eat'
10. Other starts ('t', 'i', 'k', …) die at the root: no such child
11. The trie prunes almost every path: far better than one DFS per word

04Asked at Google

3 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 Trie: Trie for prefix queries, Binary trie for maximum XOR.