Word Search II
Understanding the Problem
This is an extension of the classic Word Search problem, but instead of checking one word at a time, we need to find all words from a given list that exist on the board. A naive approach would be to run Word Search I for each word individually, but with up to 30,000 words, that repeats the full board search 30,000 times.
The real question is whether we can share work across multiple word searches. If two words share a common prefix (like "oath" and "oat"), tracing the same path twice to check both words is wasted effort. A Trie (prefix tree) solves this. By inserting all words into a Trie first, we can explore the board once and check against all words at the same time as we traverse.
Key Constraints:
1 <= m, n <= 12-> The board has at most 144 cells, small enough for backtracking with pruning.1 <= words.length <= 3 * 10^4-> Up to 30,000 words. Searching for each word individually multiplies the board traversal by 30,000, which is the main cost to eliminate.1 <= words[i].length <= 10-> Words are at most 10 characters, which bounds the backtracking depth at 10.- All strings in
wordsare unique -> The word list has no duplicates, but a single word can still be spelled by more than one board path, so the result must avoid adding it twice.
Approach 1: Brute Force (Word Search I for Each Word)
Intuition
Reuse the solution from Word Search I. For each word in the list, iterate over every cell on the board and run a DFS/backtracking search to see if that word exists. If it does, add it to the result.
This is correct but does a lot of redundant work. If the words "oath" and "oat" are both in the list, the path O -> A -> T gets traced twice, once for each word. With 30,000 words, the full board search runs 30,000 times.
Algorithm
- For each word in the word list, run Word Search I.
- For Word Search I: iterate over every cell (r, c) on the board. If board[r][c] matches the first character of the word, start a DFS.
- In the DFS, mark the current cell as visited, then try all 4 neighbors. If we match all characters of the word, return true.
- Backtrack by restoring the cell's original value.
- Collect all words that return true.
Example Walkthrough
Input:
We run a separate DFS for each word in list order.
- "oath": The only 'o' is at (0,0). From there, 'a' is at (0,1), 't' is at (1,1) below it, and 'h' is at (2,1) below that. All four characters match along adjacent cells, so "oath" is found and added to the result.
- "pea": No cell on the board holds 'p', so every starting scan fails. Not found.
- "eat": Scanning for 'e', the cell (1,0)='e' has no adjacent 'a', so that start fails. The next 'e' is at (1,3). From there, 'a' is at (1,2) and 't' is at (1,1). Match. "eat" is added.
- "rain": No cell holds 'r' adjacent to a path spelling "rain". The only 'r' is at (2,3), whose neighbors are 'k', 'e', and 'v', none of which is 'a'. Not found.
The result, in the order words were processed, is ["oath", "eat"].
Code
- Time Complexity: O(W m n * 4^L). For each of the W words, we try every cell on the m x n board as a starting point. From each cell, we explore up to 4 directions at each step, and the word can be up to L characters long.
- Space Complexity: O(L). The recursion stack goes at most L levels deep (the length of the word being searched).
This runs a full board DFS for every word in the list, retracing shared prefixes once per word. The next approach searches for all words at once: a single DFS from a cell checks against every word at the same time.
Approach 2: Trie + Backtracking (Optimal)
Intuition
Flip the problem. Instead of taking each word and searching the board for it, explore the board and check whether the current path matches any word. A Trie makes this efficient because at each DFS step we follow the corresponding child pointer in the Trie. If no child exists for the current board character, that branch is pruned immediately, since no word in the list starts with this prefix.
Insert all words into a Trie. Then, for each cell on the board, start a DFS. At each cell, check whether the Trie node has a child matching that character. If it does, move to that child and continue exploring in all 4 directions. If the current Trie node marks the end of a word, that word is a match and gets added to the results.
Two optimizations keep this fast:
- Remove found words from the Trie. Once "oath" is found, remove it from the Trie. This prevents adding duplicates and lets future DFS explorations prune earlier, since there are fewer words left to match against.
- Prune empty branches. After removing a word, if a Trie node has no remaining children, delete it. This stops the DFS from exploring paths that lead nowhere.
Removing a found word and pruning empty branches never drops a result that has not been collected yet. A node is deleted only when it has no children and no word marker, so the path through it spells no remaining word and is a prefix of no remaining word. Any later DFS that would have walked into it could only have ended in a dead end. Words still in the Trie remain reachable through their own paths, which are untouched.
Algorithm
- Build a Trie from all words in the list.
- For each cell (r, c) on the board, start a DFS with the root of the Trie.
- At each cell during DFS:
- If the cell is out of bounds, already visited, or the Trie node has no child for this character, return.
- Move to the child node in the Trie.
- If this node stores a complete word, add it to results and remove the word from the node (set it to null).
- Mark the cell as visited, recurse in all 4 directions, then restore the cell (backtrack).
- If the current Trie node has no children left after recursion, remove it from its parent (pruning).
- Return the collected results.
Example Walkthrough
Code
- Time Complexity: O(m n 4 3^(L-1)). We start DFS from each of the m n cells. From the first cell, we can go in 4 directions. For subsequent cells, we can go in at most 3 directions (we cannot go back to the cell we came from). The maximum depth is L (the length of the longest word). In practice, the Trie pruning makes this much faster because most branches are cut early.
- Space Complexity: O(W * L + L). The Trie stores all W words, each of length up to L. The recursion stack goes at most L levels deep.