Word Search II
Asked at Amazon, Meta, Microsoft, Google, Apple
Problem
Word Search II asks you to find all words from a given dictionary on an m×n board, where you can move horizontally or vertically and cannot use the same cell twice. This combines Trie + DFS/backtracking and is one of the hardest medium-to-hard problems in interview prep.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Hard | View all Amazon questions → |
| Meta | Hard | View all Meta questions → |
| Microsoft | Hard | View all Microsoft questions → |
| Hard | View all Google questions → | |
| Apple | Hard | View all Apple questions → |
How to Think About It
Brute force: for each cell on the board, start a DFS searching for every word in the dictionary. This is extremely slow — O(m × n × 4^L × W) where L is max word length and W is number of words.
Trie optimization: build a Trie from the dictionary. As you DFS on the board, traverse the Trie simultaneously. If the current path is not a prefix of any word, prune immediately. This avoids exploring dead ends.
DFS + backtracking: from each cell, explore all 4 directions. Mark visited cells (e.g., set to #), recurse, then unmark. When you reach a Trie node marked as isEnd, you found a word — add it to results and unmark the node (to avoid duplicates).
Pruning: after finding a word, remove it from the Trie (unmark isEnd). If a Trie node has no children left, remove it entirely. This prevents revisiting the same words and speeds up the search.
Edge cases: empty board, empty word list, words that share prefixes, board with repeated letters, words longer than the board can accommodate.
Optimal Approach
- Build a Trie from all words in the dictionary.
- For each cell on the board, start a DFS traversal.
- In DFS: if current cell is out of bounds or already visited, return. If the Trie has no child for this character, return. Mark cell as visited, move to the Trie child.
- If the Trie node is
isEnd, add the word to results and unmarkisEnd. - Recurse in all 4 directions.
- Backtrack: restore the cell character, return from Trie node.
Time: O(m × n × 4 × 3^(L-1)) where L is max word length — each cell branches 4, but after the first step it's at most 3. Space: O(W × L) for the Trie + O(L) recursion stack.
What Trips People Up in Real Interviews
Not using a Trie — searching for each word independently is too slow. The Trie shares prefix structure and prunes the search space.
Forgetting to backtrack. If you don't unmark visited cells, the DFS cannot explore other paths through the same cell.
Not pruning the Trie after finding a word. Without pruning, you may find the same word multiple times or waste time on paths that led to already-found words.
Using a HashSet instead of a Trie. A HashSet tells you if a word exists but doesn't help with prefix pruning during DFS.
Stack overflow from deep recursion on large boards. For very large boards, consider iterative DFS with an explicit stack.
Solution Code
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def buildTrie(words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word
return root
def findWords(board, words):
root = buildTrie(words)
result = []
rows, cols = len(board), len(board[0])
def dfs(r, c, node):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
ch = board[r][c]
if ch == '#' or ch not in node.children:
return
node = node.children[ch]
if node.word:
result.append(node.word)
node.word = None
board[r][c] = '#'
dfs(r + 1, c, node)
dfs(r - 1, c, node)
dfs(r, c + 1, node)
dfs(r, c - 1, node)
board[r][c] = ch
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return resultFrequently Asked Questions
What is the Word Search II problem?
Word Search II asks you to find all words from a given dictionary on an m×n board, where you can move horizontally or vertically and cannot use the same cell twice. This combines Trie + DFS/backtracking and is one of the hardest medium-to-hard problems in interview prep.
How do you solve Word Search II?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Word Search II?
Word Search II is asked at Amazon, Meta, Microsoft, Google, Apple. It is a hard difficulty problem.
What are common mistakes on Word Search II?
- Not using a Trie — searching for each word independently is too slow. The Trie shares prefix structure and prunes the search space.
- Forgetting to backtrack. If you don't unmark visited cells, the DFS cannot explore other paths through the same cell.
- Not pruning the Trie after finding a word. Without pruning, you may find the same word multiple times or waste time on paths that led to already-found words.
- Using a HashSet instead of a Trie. A HashSet tells you if a word exists but doesn't help with prefix pruning during DFS.
- Stack overflow from deep recursion on large boards. For very large boards, consider iterative DFS with an explicit stack.