Word Search II
Given a letter grid and a list of words, return all words from the list that can be formed by paths of adjacent cells without reusing a cell. The list can contain thousands of words.
- 1 ≤ m, n ≤ 12
- 1 ≤ words.length ≤ 3 · 10^4
- 1 ≤ word length ≤ 10
- All words distinct
- Many words searched on the same board — one DFS per word is too slow
- All words share prefixes → build a trie
- Prune DFS when the current path is not a trie prefix
Prefix questions over a set of strings are answered by walking a tree keyed by characters, costing O(L) per query regardless of how many words are stored. It also lets a grid DFS abort as soon as the current path is not a prefix of any word, which is what makes multi-word search feasible.
Insert all words into a trie. DFS from every cell, descending the trie in lock-step with the board path: stop immediately when the current letter has no child, and record a word when a terminal node is reached (clearing its flag to avoid duplicates). Mark cells visited on the way down and restore them on return. Optionally delete trie leaves once matched so dead branches vanish.
- Running Word Search for each word costs O(W · m · n · 3^L) and times out at 3 · 10^4 words. Aho-Corasick is overkill since paths, not a linear text, are searched.