212. Word Search II - Detailed Explanation
Problem Statement
Description:
You are given an (m \times n) grid (called board) of characters and a list of strings called words. Your task is to find all the words from the list that can be formed in the grid. A word is formed by connecting letters sequentially in adjacent cells (neighbors can be up, down, left, or right) and the same cell cannot be used more than once for constructing a single word.
Examples:
-
Example 1:
Input:
board = [ ["o","a","a","n"], ["e","t","a","e"], ["i","h","k","r"], ["i","f","l","v"] ] words = ["oath","pea","eat","rain"]Output:
["oath", "eat"]Explanation:
- The word "oath" can be constructed along the path: ( (0,0) \rightarrow (1,0) \rightarrow (2,1) \rightarrow (3,2) ) (using coordinates ((row, column))).
- The word "eat" can be constructed along a valid path in the grid.
- The words "pea" and "rain" cannot be formed according to the rules.
-
Example 2:
Input:
board = [["a","b"],["c","d"]] words = ["abcb"]Output:
[]Explanation:
- The word "abcb" cannot be constructed because it would require using the same cell more than once.
Constraints:
- (1 \leq m, n \leq 12) (the board dimensions are relatively small)
- (1 \leq \text{words.length} \leq 3 \times 10^4)
- (1 \leq \text{words}[i].length \leq 10)
- Each word and board cell contains only lowercase English letters.
Hints Before Diving into the Solution
-
Hint 1:
A naive approach would be to try and search for each word on the board using DFS. However, since the list of words can be large, this approach would be too slow. Notice that many words share common prefixes. -
Hint 2:
Using a Trie (prefix tree) to store all the words allows you to perform efficient prefix checking during DFS. This helps you quickly prune search paths that do not lead to any valid word. -
Hint 3:
Use backtracking while traversing the board and mark cells as visited to avoid using the same cell twice in one word construction. After exploring a path, make sure to backtrack (unmark) the cell.
Approaches
Approach 1: Brute-Force DFS for Each Word (Not Recommended)
Idea:
- For every word in the list, run a DFS from every cell in the board to see if the word can be formed.
Drawbacks:
- With up to (3 \times 10^4) words, this approach becomes prohibitively slow due to repeated searches and overlapping subproblems.
Approach 2: Trie-Based Backtracking (Optimal)
Idea:
-
Build a Trie:
Insert all words into a Trie. Each node in the Trie represents a letter, and paths from the root represent prefixes. Mark nodes that represent complete words. -
DFS from Each Cell:
Start a DFS from every cell on the board. As you traverse, follow the corresponding Trie nodes.- If a cell’s character is not in the current Trie node, prune that DFS path.
- If you reach a Trie node that marks the end of a word, add that word to the result.
-
Marking and Backtracking:
Temporarily mark cells as visited during DFS to avoid reuse. Restore the cell’s value after exploring that path. -
Trie Pruning (Optional):
Once a word is found, you can optionally remove it from the Trie to avoid duplicates and reduce future search space.
Benefits:
- Efficiency:
Only explore paths that could lead to a valid word (pruning using Trie). - Avoids Repetition:
Shares common prefix searches for multiple words.
Code Implementation
Python Code
Java Code
Complexity Analysis
- Time Complexity:
-
Building the Trie takes (O(W \times L)), where (W) is the number of words and (L) is the average word length.
-
The DFS from each cell in the board takes (O(m \times n \times 4^{L'})) in the worst case, where (L') is the maximum depth of DFS (bounded by the word length).
-
However, using the Trie to prune paths considerably reduces the average-case time complexity.
-
- Space Complexity:
-
The Trie uses (O(W \times L)) space.
-
The DFS recursion uses (O(m \times n)) in the worst-case stack space (if the board is fully explored), though typically it is much smaller.
-
Step-by-Step Walkthrough & Visual Example
Consider the board:
[
["o", "a", "a", "n"],
["e", "t", "a", "e"],
["i", "h", "k", "r"],
["i", "f", "l", "v"]
]
and the words: (["oath", "pea", "eat", "rain"]).
Step 1: Build the Trie
- Insert each word into the Trie. For instance, the path for "oath" is created:
- root → 'o' → 'a' → 't' → 'h' (mark word = "oath").
Step 2: Start DFS
- For each cell in the board, start DFS.
- At cell ((0,0)) with letter 'o':
- 'o' exists in Trie → move to child node.
- Check adjacent cells ((1,0)), ((0,1)) for the next letter in the Trie (for "oath", next letter is 'a').
- Continue recursively, marking cells as visited and following the Trie.
- When a complete word is found (i.e. at node where word is stored), add it to the result.
- At cell ((0,0)) with letter 'o':
Step 3: Backtracking
- Restore cells after exploring each DFS branch to allow reuse for other words.
- Prune paths if a cell’s letter is not in the Trie node children.
Result:
After DFS from all cells, the valid words found are added to the result (e.g., "oath" and "eat").
Common Mistakes
-
Not Marking Visited Cells:
Failing to mark cells as visited can lead to using the same cell twice in one path. -
Missing Trie Pruning:
Not leveraging the Trie to prune paths leads to unnecessary DFS exploration. -
Duplicate Word Entries:
Without proper handling (e.g., clearing the found word in the Trie), the same word might be added multiple times. -
Boundary Conditions:
Make sure to check array boundaries during DFS to avoid index errors.
Edge Cases & Alternative Variations
-
Edge Case 1:
An empty board or an empty word list should return an empty list. -
Edge Case 2:
A board with one cell and a word list containing single-letter words. -
Alternative Variation:
The simpler "Word Search" problem (Word Search I) where you check for only one word. This problem extends that to multiple words and requires efficient prefix checking.
Related Problems for Further Practice
-
Word Search I:
Searching for a single word in a grid using DFS. -
Boggle Game:
Finding all valid words in a grid given a dictionary. -
Trie Implementations:
Practice problems that involve building and querying Tries. -
Backtracking Problems:
Other puzzles like Sudoku or combinations where backtracking is essential.
GET YOUR FREE
Coding Questions Catalog
