Trie — Word Search II
↗ LeetCode: Word Search II · Hard · pattern chapter →
Given board[m][n] of letters and a dictionary words, return all words in words that can be traced through adjacent cells (no cell reused within a single word).
Example 1 — board=[[o,a,a,n],[e,t,a,e],[i,h,k,r],[i,f,l,v]], words=["oath","pea","eat","rain"] → ["oath","eat"]Example 2 — board=[["a","b"],["c","d"]], words=["abcb"] → [] (needs cell reuse) Example 3 — board=[["a"]], words=["a"] → ["a"]
Constraints — 1 ≤ m, n ≤ 12; up to 3·10⁴ words; each ≤ 10 chars. Brute DFS-per-word is O(k·m·n·4^L) = 3·10⁴·144·4^10 ≈ 4·10¹² ops = TLE (minutes). Trie collapses to a single DFS — O(m·n·4^L) = ~10⁸ ops = ~1s.
Interview timer00:00
Approach 1 — DFS per word
Intuition. For each word, DFS from every cell; return true if the whole word can be traced.
List<String> findWordsBrute(char[][] b, String[] words) {
List<String> res = new ArrayList<>();
for (String w : words) if (exists(b, w)) res.add(w);
return res;
}
// exists = classic Word Search I DFS. O(m·n·4^L) per word.Complexity — Time O(k · m·n · 4^L) where k = #words, L = max length; Space O(L) stack.
At k=3·10⁴, L=10 this is astronomical. TLE.
Approach 2 — DFS + pruning by common prefix (shared traversal)
Intuition. Many words share prefixes. Group them by prefix and traverse once per shared prefix.
But managing shared prefixes explicitly is exactly what a trie does — which is Approach 3.
Approach 3 — Trie + one DFS pass
Insight from brute. Load all words into a trie. Now DFS from every cell once; at each step, check the child character in the trie. If absent, prune the whole subtree.
Optimization — mark a trie node's word field when we collect it, and set to null afterwards, so we don't collect duplicates.
Trap — restore the cell after DFS returns (Word Search discipline). Otherwise sibling paths can't reuse a cell.
class TrieNode {
Map<Character, TrieNode> ch = new HashMap<>();
String word; // set at end-of-word
}
List<String> findWords(char[][] b, String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode cur = root;
for (char c : w.toCharArray()) cur = cur.ch.computeIfAbsent(c, k -> new TrieNode());
cur.word = w;
}
List<String> out = new ArrayList<>();
for (int r = 0; r < b.length; r++)
for (int c = 0; c < b[0].length; c++)
dfs(b, r, c, root, out);
return out;
}
void dfs(char[][] b, int r, int c, TrieNode node, List<String> out) {
if (r < 0 || r >= b.length || c < 0 || c >= b[0].length) return;
char ch = b[r][c];
TrieNode next = node.ch.get(ch);
if (next == null) return;
if (next.word != null) { out.add(next.word); next.word = null; } // dedup
b[r][c] = '#';
dfs(b, r + 1, c, next, out); dfs(b, r - 1, c, next, out);
dfs(b, r, c + 1, next, out); dfs(b, r, c - 1, next, out);
b[r][c] = ch;
}Complexity — Time O(m·n · 4^L) — the whole word list is walked in one traversal; Space O(#chars in dict) for the trie.
Try it yourself
Complexity summary
| Approach | Time | Space |
|---|---|---|
| DFS per word | O(k · m·n · 4^L) | O(L) |
| Trie + one DFS | O(m·n · 4^L) | O(dict) |
When to use which
- Many words, short board → trie wins by orders of magnitude.
- One word, big board → plain DFS is fine.
- Interviewer probes "any way to prune early?" → the trie IS the pruner.
Related problems (same ladder applies)
- Word Search I — one word, DFS only
- Concatenated Words — trie + DP
- Replace Words — trie for shortest root prefix
- Stream of Characters — trie in reverse