Word Search II
Word Search II: find which words from a list exist as adjacent-cell paths in a letter grid (no cell reused per word).
- m == board.length
- n == board[i].length
- 1 <= m, n <= 12
- board[i][j] is a lowercase English letter.
- 1 <= words.length <= 3 * 10⁴
- 1 <= words[i].length <= 10
- words[i] consists of lowercase English letters.
- All the strings of words are unique.
Intuition
Word search ii asks which words from a list appear in a letter grid as paths of adjacent cells, with no cell reused within a single word. Running a separate grid search per word repeats the same walks over and over — the prefix "ca" is re-traced for every word beginning with it.
The fix is to search for all words at once, and a trie is what makes that possible. Insert every word into a trie, then walk the grid and the trie in lockstep: a step onto a neighbouring cell is only taken if the trie has a child for that letter.
That single condition is where all the pruning comes from:
- The moment the current path is not a prefix of any word, the trie has no matching child and the search stops immediately.
With a per-word search you would keep walking until the word ran out. Here the search dies as soon as no word can possibly match, and every word is being tested simultaneously.
Two details matter in the implementation. Store the whole word at its terminal trie node rather than a boolean flag — then finding a match gives you the answer directly with no path reconstruction. And after recording a match, null that marker so the same word is not reported again when reached from another cell.
An optional refinement is to prune leaf nodes once their word has been found. The trie shrinks as the search progresses, which measurably speeds up large inputs.
One trie walked alongside the grid DFS, instead of running Word Search once per word. The trie collapses shared prefixes so a dead end kills every word beneath it at once. Popping the "$" marker on a hit is a neat de-duplication trick — the word can never be reported twice.
Approach
Before reading on: price up what the direct approach costs here, then ask what has to be undone after each choice so the next branch starts clean. Aim for O(R·C·4^L) time and O(total chars) space.
See why per-word search wastes work
Searching each word separately re-traces every shared prefix once per word. A trie tests all words simultaneously, so a shared prefix is walked once no matter how many words begin with it.
Store the word at its terminal node
Insert every word, placing the full string at its end node rather than a boolean. When the search reaches that node, the answer is already there — no need to reconstruct the path.
Start a DFS from every cell
For each grid cell whose letter is a child of the trie root, begin a search. Cells whose letter starts no word are skipped immediately, which prunes a large fraction of starting points.
Move through grid and trie together
Step to a neighbour only if the trie node has a child for that letter. This is the pruning — the search dies the instant the current path stops being a prefix of any word.
Mark and unmark the visited cell
Overwrite the cell with a sentinel before recursing and restore it afterwards, since no cell may be reused within one word. The restore is mandatory — without it, cells consumed by one word become unavailable to every later one.
Null the marker after a match
On reaching a node holding a word, record it and set that marker to null. Without this the same word is reported once per grid path that spells it, producing duplicates in the output.
Cost of the combined search
Building the trie is O(total characters). The search is O(rows × cols × 4^L) in the worst case for maximum word length L, but trie pruning cuts the real branching factor far below 4 — which is what makes this practical where per-word search is not.
Solution & live demo
Common pitfalls
Searching each word independently
for w in words:
if exist(board, w): res.append(w)# one trie, one DFS over the grid
With thousands of words sharing prefixes, that repeats the same failing exploration for every one of them. The trie makes the grid pay for each distinct prefix once, no matter how many words start with it.
Returning instead of continuing after a match
if w: res.append(w); return
if w: res.append(w) # keep exploring
A matched word may be the prefix of a longer one also present in the grid. Returning at the first hit stops the walk and silently drops those longer words.
Forgetting to restore the cell
board[r][c] = "#" for ...: dfs(...)
board[r][c] = "#" for ...: dfs(...) board[r][c] = ch
The # marks the cell as in-use for the current path only. Leaving it set makes the cell permanently unusable, so words needing it via a different route are never found.
Edge cases
Clearing the end-node marker on first find prevents duplicates.
Interior end-markers fire without stopping the deeper search.
Temporary '#' marking blocks revisits; restored on backtrack.