Word Search II
Problem
m x n grid of lowercase letters and a list of distinct
words. Return every word that can be spelled by a path of
horizontally or vertically adjacent cells, where a single cell may be used
at most once per word. The answer may be in any order.oaan/etae/ihkr/iflv, [oath,pea,eat,rain]Output[eat,oath]ab/cd, [abcb]Output[]1 ≤ m, n ≤ 12 · 1 ≤ words.length ≤ 3·104 · 1 ≤ word length ≤ 10 · words are unique, lowercase only
Try it yourself
class Solution {
public List<String> findWords(char[][] board, String[] words) {
}
}
Instinct Many words, shared prefixes, and questions like "starts with", autocomplete, wildcard match or "search a board for all these words" - build a prefix tree.
Memory hack Words share their beginnings, so store each beginning once - walk one letter per step, and an end flag marks where a real word stops.
Open the Trie guide →Approaches
Brute ForceWord Search (DFS) for Every Word
O(W·m·n·3L)Space O(L)Solve Word Search I for each word: try every cell as a start and backtrack in
4 directions, marking path cells with '#'. Words sharing a prefix
redo the same exploration again and again.
public List<String> findWords(char[][] board, String[] words) { List<String> result = new ArrayList<>(); for (String word : words) { search: for (int i = 0; i < board.length; i++) for (int j = 0; j < board[0].length; j++) if (dfs(board, word, i, j, 0)) { result.add(word); break search; } } return result; } private boolean dfs(char[][] b, String word, int i, int j, int idx) { if (idx == word.length()) return true; if (i < 0 || j < 0 || i >= b.length || j >= b[0].length || b[i][j] != word.charAt(idx)) return false; char tmp = b[i][j]; b[i][j] = '#'; // mark visited boolean found = dfs(b, word, i + 1, j, idx + 1) || dfs(b, word, i - 1, j, idx + 1) || dfs(b, word, i, j + 1, idx + 1) || dfs(b, word, i, j - 1, idx + 1); b[i][j] = tmp; // backtrack return found; }
Simple, but with 3·104 words the repeated grid scans time out.
OptimalTrie + Backtracking with Pruning
O(m·n·3L + S)Space O(S)Insert all words into a Trie (S = total letters); a node stores the full
word that ends there. DFS from every cell, moving the Trie pointer with
the path: a missing child kills the branch. On a hit, add the word and null it (no
duplicates); a node left with no word and no children is detached.
class TrieNode { TrieNode[] next = new TrieNode[26]; String word; // set if a word ends here int children; // number of non-null children } public List<String> findWords(char[][] board, String[] words) { TrieNode root = new TrieNode(); for (String w : words) { TrieNode node = root; for (char c : w.toCharArray()) { int k = c - 'a'; if (node.next[k] == null) { node.next[k] = new TrieNode(); node.children++; } node = node.next[k]; } node.word = w; } List<String> result = new ArrayList<>(); for (int i = 0; i < board.length; i++) for (int j = 0; j < board[0].length; j++) dfs(board, i, j, root, result); return result; } private void dfs(char[][] b, int i, int j, TrieNode parent, List<String> res) { if (i < 0 || j < 0 || i >= b.length || j >= b[0].length || b[i][j] == '#') return; char c = b[i][j]; TrieNode node = parent.next[c - 'a']; if (node == null) return; // no word has this prefix if (node.word != null) { res.add(node.word); node.word = null; } // report once b[i][j] = '#'; dfs(b, i + 1, j, node, res); dfs(b, i - 1, j, node, res); dfs(b, i, j + 1, node, res); dfs(b, i, j - 1, node, res); b[i][j] = c; if (node.word == null && node.children == 0) { // exhausted branch: prune parent.next[c - 'a'] = null; parent.children--; } }
One shared search for all words; pruning makes the Trie shrink as words are found.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Word Search (DFS) for Every Word | O(W·m·n·3L) | O(L) |
| Optimal | Trie + Backtracking with Pruning | O(m·n·3L + S) | O(S) |
- Forgetting to restore
board[i][j]after the DFS — later searches see'#'. - Not clearing
node.word— the same word is reported from several paths. - Computing
'#' - 'a'as an index — check the visited mark before the Trie lookup.
- Start from Word Search I per word, then point out the shared-prefix waste.
- Explain why the Trie turns W separate searches into one simultaneous search.
- Mention pruning dead leaves as the extra optimisation that passes the hardest tests.