Word Search II
Last Updated: March 29, 2026
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 becomes extremely wasteful.
The real question is: can we share work across multiple word searches? If two words share a common prefix (like "oath" and "oat"), we should not trace the same path twice just to check both words. This is exactly the kind of problem where a Trie (prefix tree) shines. By inserting all words into a Trie first, we can explore the board once and check against all words simultaneously as we traverse.
Key Constraints:
1 <= m, n <= 12-> The board can be up to 12x12 = 144 cells. This is small enough for backtracking with pruning.1 <= words.length <= 3 * 10^4-> Up to 30,000 words. Searching for each word individually would multiply the cost, so we need a smarter approach.1 <= words[i].length <= 10-> Words are at most 10 characters long. This limits the depth of our backtracking.- All strings in
wordsare unique -> No need to worry about duplicate results from the word list itself, though we still need to avoid adding the same word twice if multiple board paths spell it.
Approach 1: Brute Force (Word Search I for Each Word)
Intuition
The simplest idea is to 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 works correctly but does a lot of redundant work. If the words "oath" and "oat" are both in the list, we would trace the path O -> A -> T twice, once for each word. And if we have 30,000 words, we run the full board search 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:
For each word, we run a separate DFS on the board. For "oath", we start at (0,0)='o', move to (0,1)='a', then (1,1)='t', then (2,1)='h'. Found. For "pea", there is no 'p' on the board. Not found. For "eat", we start at (1,3)='e', move to (1,2)='a', then (1,1)='t'. Found. For "rain", no valid path exists.
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).
We run a full board DFS for every single word in the list. Many words share common prefixes, yet we trace those paths independently for each word. What if we could search for all words at once, so that a single DFS from any cell checks against every word simultaneously?
Approach 2: Trie + Backtracking (Optimal)
Intuition
The key insight is to flip the problem. Instead of taking each word and searching the board for it, we explore the board and check if the current path matches any word. A Trie makes this efficient because at each step of the DFS, we just follow the corresponding child pointer in the Trie. If no child exists for the current board character, we prune that branch immediately, meaning no word in our list starts with this prefix.
Here is how it works: insert all words into a Trie. Then, for each cell on the board, start a DFS. At each cell, check if the Trie node has a child matching that character. If yes, move to that child and continue exploring in all 4 directions. If the current Trie node marks the end of a word, we found a match and add it to our results.
There are two important optimizations that make this fast in practice:
- Remove found words from the Trie. Once we find "oath", we remove it from the Trie. This prevents adding duplicates and, more importantly, it means future DFS explorations can prune earlier because there are fewer words to match against.
- Prune empty branches. After removing a word, if a Trie node has no remaining children, we can delete it. This prevents the DFS from exploring paths that lead nowhere.
The Trie acts as a shared prefix filter for all words simultaneously. Instead of asking "does this board path match word 1? word 2? word 3?", we ask "does this board path match any prefix in the Trie?" at each step. If no word starts with the current path, we prune immediately. The Trie lets us reject dead-end paths for all 30,000 words in O(1) per character.
The pruning optimization is the cherry on top. As we find words, we shrink the Trie. This means later DFS explorations have fewer prefixes to match against, and they prune earlier. In the best case, once all words are found, the Trie is empty and the remaining DFS calls terminate instantly at the root.
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:
a. If the cell is out of bounds, already visited, or the Trie node has no child for this character, return.
b. Move to the child node in the Trie.
c. If this node stores a complete word, add it to results and remove the word from the node (set it to null).
d. Mark the cell as visited, recurse in all 4 directions, then restore the cell (backtrack).
e. 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.