Canonical Deep-Dive: Word Search II

Problem: Word Search II (https://leetcode.com/problems/word-search-ii/) The lesson: the fusion of a trie (this week) with the backtracking grid search (Week 9), where the trie is not a lookup table but a pruning device.

This is a guided walk-through, not an answer key. It explains how to think about combining a trie with a grid DFS, why the trie is what makes the search tractable, and how to carry over the mark/recurse/unmark rhythm from Week 9. It stops short of an assembled, paste-runnable function on purpose. You write the actual Python yourself, in your own work repo. The tutor will not confirm your code; LeetCode’s judge will.

Restated: you are given an m by n board of single characters and a list of target words. Return every word from the list that can be spelled by a path through the board, where each step moves to a horizontally or vertically adjacent cell and no single cell is used more than once in one word. The answer is the set of words found; order does not matter, and each found word appears once. A board can hold tens of thousands of cells and the word list can be long, with words up to about ten characters.

Why the obvious approach is too slow, and what saves it

The obvious idea borrows directly from Word Search (the single-word problem in Week 9): for each word, run a backtracking search over the whole board looking for that word. That is correct, but it rescans the entire board once per word, and worse, it explores long dead paths for every word independently. If two target words share the prefix "app", the naive approach re-walks the board spelling "app" separately for each of them, discovering only at the end that one continues and the other does not.

The fix is to flip the relationship. Instead of asking “for this one word, is it on the board”, you walk the board once and ask “do the characters I am spelling right now still lead toward any target word”. The structure that answers that question in O(1) per step is a trie built from all the target words. The trie is shared across every word, so the shared prefix "app" is walked once, and the instant the characters you have spelled are not a prefix of any target word, you stop. That early stop is pruning, and it is what turns a hopeless per-word rescan into a single guided search.

Insight 1: build a trie of the words, not an index of the board

The first move is to put all the target words into a trie. A trie node is a dict mapping each next character to its child node, plus a marker for “a word ends here”. Inserting a word walks its characters from the root, creating any missing children, and marks the final node. After inserting every word, the trie is a compact map of every prefix any target word can have: if a sequence of characters is not a path in the trie, then no target word starts with that sequence, full stop.

A small refinement that pays off: instead of (or in addition to) a boolean end-of-word flag, store the actual word string at its end node. Then, when your board walk arrives at an end node, you immediately know which word to record without reconstructing it from the path. This is a common and clean way to write Word Search II.

The trie is built once, before you touch the board, and it costs time proportional to the total number of characters across all words. That build cost is the only preprocessing you do.

Insight 2: DFS the board following trie edges

Now walk the board. Carry over the exact rhythm from Week 9’s Word Search: from a starting cell, you spell characters by moving to adjacent cells, marking each cell as used so one word cannot reuse a cell, and unmarking it when you back out. The single change that makes this Word Search II is that you carry a trie node alongside your position on the board, and you only step onto a neighbor if that neighbor’s character is a child of the current trie node.

Walk the rhythm, beat by beat. You write the code; this is the shape.

State you carry: the current cell (r, c) and the current trie node (the node reached by the characters spelled so far).

1. Check the trie edge. Look at the character in the current cell. If it is not a child of the current trie node, this path cannot spell any target word, so return immediately. This is the prune, and it is the whole point: you abandon the branch the moment the prefix leaves the trie, before exploring any further.

2. Step into the child. Move to the child node for this character. If that child is an end-of-word node, you have spelled a complete target word: record it (add it to a result set, or read off the stored word string). Recording does not stop the search, because a found word can be a prefix of a longer target word still ahead.

3. Mark, recurse into neighbors, unmark. Mark the current cell as used (overwrite it with a sentinel like "#", or keep a visited set). Recurse into each of the four adjacent cells that is in bounds and not currently used, each time passing the child node you stepped into. After the recursive calls return, unmark the cell (restore its character) so a different word’s path is free to use it again.

You launch this search from every cell of the board, each time starting at the trie root, because a word can begin anywhere.

Insight 3: dedup the results with a set

Because the same word can sometimes be reachable by more than one path, and because you record a word as soon as you reach its end node, collect found words in a set rather than a list. The problem wants each found word once and does not care about order, so a set is the natural container; convert it to a list at the very end to return. (An alternative is to remove a word from the trie once found, which both dedups and prunes the trie further, but a result set is the simpler thing to reach for first.)

The key insight, in one sentence

Build one trie from all the target words, then walk the board once with the Week 9 mark/recurse/unmark rhythm while carrying a trie node, stepping only onto neighbors whose character is a trie child and abandoning any path the moment its prefix leaves the trie; record a word when you reach an end-of-word node, dedup with a set. The trie is shared across all words and prunes every dead path early, which is what collapses a per-word rescan into a single guided search.

Exact complexity

Let the board have cells cells and let L be the length of the longest target word.

• Building the trie: O(total word length), the sum of the lengths of all target words, since insertion walks each word’s characters once.
• The DFS: O(cells * 4 * 3^(L-1)). You may launch the search from each of the cells cells. From a starting cell the first step has up to 4 directions to move, but every step after the first has only 3 real choices, because one of the four neighbors is the cell you just came from and is currently marked used. So a single search path branches like 4 then 3, 3, 3, …, which is 4 * 3^(L-1) over a path of length up to L. The trie is what bounds the depth at L: the moment the spelled prefix is not in the trie you stop, so no path runs deeper than the longest word. Multiplying the per-cell search by the cells starting cells gives O(cells * 4 * 3^(L-1)).

State both halves in an interview: the trie build is linear in the total characters of the word list, and the search is the grid DFS bounded in depth by the longest word, which is where the 3^(L-1) branching and the L cap both come from. Naming why it is 3 and not 4 after the first step (you cannot revisit the cell you came from) and why the depth is bounded by L (the trie prunes any deeper path) is exactly the discrimination interviewers are listening for.

Your work this week

1. Implement Word Search II yourself, in your own work repo (for example word-search-ii.py). Build the trie from the words (store the word string at its end node for convenience), then DFS from every cell carrying a trie node, prune when the character is not a trie child, mark/recurse/unmark on the grid, and collect found words in a set. Do not copy a solution; build it from the three insights above.
2. Test the provided example yourself: board [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]] with words ["oath","pea","eat","rain"] returns {"oath", "eat"} (in any order). Then test the edge cases: a single-cell board, a word longer than the board can hold (found nothing), and two words that share a prefix (confirm the shared prefix is walked once and both are found if both are present).
3. Then make one improvement and feel its effect: remove a word from the trie (or mark its end node consumed) the moment you find it, so the search never re-finds it and can prune subtrees that no longer lead anywhere. Convince yourself the answers are unchanged and the search does less work.
4. Commit with a five-question debrief in the message. In answer 3, state the exact complexity above and explain, in one sentence each, why each step after the first branches into 3 and not 4, and why the trie bounds the DFS depth at the longest word length L.

When you can explain, from memory and with no AI open, why the trie is a pruning device rather than a lookup table, how the Week 9 mark/recurse/unmark rhythm carries over unchanged, and where the O(cells * 4 * 3^(L-1)) search bound comes from, you own this problem. That explanation is exactly what an interviewer will ask for, and it is the clearest demonstration in the course of two patterns fused into one.