Word Search II hard
Description
Given an m × n board of characters and a list of words, return all words that can be formed by a path of adjacent (up/down/left/right) cells, using each cell at most once per word.
Examples
> board = [["o","a","a","n"],
["e","t","a","e"],
["i","h","k","r"],
["i","f","l","v"]]
words = ["oath","pea","eat","rain"]
Output: ["oath","eat"]Constraints
1 <= m, n <= 121 <= words.length <= 3 × 10^4, word length ≤ 10, lowercase.
Intuition — why a trie, not repeated Word Search I
The naive approach runs a separate grid DFS for each word — O(words × cells × 4^L). With 30,000 words that’s hopeless. The fix: put all words into one trie, then DFS the grid once, descending the trie in lockstep with the path. The instant the current grid path isn’t a prefix of any word, the trie has no matching child and you prune immediately — one walk handles all words, and dead branches die fast.
Code
Two tricks make this fast and clean: (1) store the full word at its end node so when you hit an end-of-word you can emit it directly — no need to track the path string. (2) Clear the word after emitting (del/null) to dedupe and to shrink the trie as you go, which prunes future work. The trie turns “test 30,000 words” into “walk the grid once, guided by what’s still possible.”
Analysis
- Time:
O(cells × 4 × 3^(L−1))in the worst case (L = max word length), but the trie prunes branches with no matching prefix, so it’s far faster in practice. Building the trie isO(total word characters). - Space:
O(total word characters)for the trie +O(L)recursion.
Same skin
- Add & Search Word — also “trie + DFS,” but the DFS walks a query string instead of a grid.
- Word Search I — the single-word version; this problem is why you upgrade to a trie.
- Backtracking on a grid (Day 16) — the DFS + mark-visited + restore skeleton is pure backtracking, with the trie as the pruning oracle.