Word Search II

Word Search II

What is this problem about?

"Word Search II" is an extension of the classic word search grid problem. Instead of looking for a single word, you are given a 2D board of characters and a list of words. Your task is to find all the words from the list that can be constructed by sequentially adjacent cells in the board. A cell cannot be reused within a single word.

Why is this asked in interviews?

This is a standard "Hard" problem because it tests your ability to combine two major data structures/algorithms: Tries and DFS with Backtracking. Companies like Uber and Amazon ask this to see if you can optimize a search. If you ran a standard DFS for every word in the list, it would be extremely slow. Using a Trie allows you to search for multiple words simultaneously as you traverse the grid.

Algorithmic pattern used

The optimal approach uses a Trie (Prefix Tree).

1. Insert all the dictionary words into a Trie.
2. For each cell in the board, start a DFS.
3. As you move through the board, move through the corresponding nodes in the Trie.
4. If you reach a node that marks the end of a word, you've found a match!
5. Backtrack (unmark visited cells) to explore other paths.
6. Optimization: Remove a word from the Trie once it's found to avoid finding the same word multiple times.

Example explanation

Board:

o a n n
e t a e
i h k r

Words: ["oath", "pea", "eat"].

1. Start at o: In Trie? Yes.
2. Move to a: In Trie? Yes.
3. Move to t: In Trie? Yes.
4. Move to h: In Trie? Yes. Word oath found!
5. Start at e: In Trie? Yes.
6. Move to a: In Trie? Yes.
7. Move to t: In Trie? Yes. Word eat found!

Common mistakes candidates make

• Not using a Trie: Attempting to solve it word-by-word, which leads to O(W * M * N * 4^L) complexity, where W is the number of words.
• Trie node management: Forgetting to store the actual word at the end of the Trie node, making it harder to collect found words.
• Visited set overhead: Using a separate Set for visited cells instead of modifying the board in-place (and then reverting it), which is much faster.

Interview preparation tip

Practice implementing a Trie from scratch. For "Word Search II," make sure you understand how to "prune" the Trie—deleting nodes that no longer lead to any words—to keep the search space as small as possible.