#212
Word Search II
Hard Trie-guided grid DFS
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Find every word from a list that can be traced in a letter grid by adjacent moves without reusing a cell.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: find all dictionary words in a letter grid.
Why this works: one trie for all the words; one DFS over the grid that follows trie edges, so dead ends stop early.
Example: words ["oath", "eat"] on a board
DFS from 'o' follows o → a → t → h → found "oath"from 'e' → a → t → found "eat"
✦Hints open one at a time
Running Word Search once per word is too slow.
Put all words in a trie and DFS the grid once, following trie edges.
Remove found words from the trie (or clear the word) so you don't report them twice, and prune empty branches.
↗Approach
Build a trie storing the full word at its end node. DFS from every cell: move into the child for the cell's letter; if the node holds a word, record it and clear it. Mark cells while on the path and restore after.
</>Solution (Java)
import java.util.*;
class Solution {
private static class Node {
Node[] next = new Node[26];
String word;
}
public List<String> findWords(char[][] board, String[] words) {
Node root = new Node();
for (String w : words) {
Node cur = root;
for (char c : w.toCharArray()) {
if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
cur = cur.next[c - 'a'];
}
cur.word = w;
}
List<String> res = new ArrayList<>();
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
dfs(board, r, c, root, res);
return res;
}
private void dfs(char[][] b, int r, int c, Node parent, List<String> res) {
if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] == '#') return;
char ch = b[r][c];
Node node = parent.next[ch - 'a'];
if (node == null) return; // no word continues this way
if (node.word != null) {
res.add(node.word);
node.word = null; // report once
}
b[r][c] = '#';
dfs(b, r + 1, c, node, res);
dfs(b, r - 1, c, node, res);
dfs(b, r, c + 1, node, res);
dfs(b, r, c - 1, node, res);
b[r][c] = ch;
}
}!Common mistake
Adding the same word several times when it can be traced in more than one way.
Complexity
- Time: O(m·n·4·3^(L−1)) worst case, much faster with pruning.
- Space: O(total characters in words).
Topic: Trie
🎬 Episode 97: video coming soon