212. Word Search II
Problem Description
You are given a 2D board of characters (an m x n
grid) and a list of words. Your task is to find all words from the list that can be formed on the board.
To form a word on the board:
- Start from any cell on the board
- Move to adjacent cells (horizontally or vertically neighboring cells only - no diagonal moves)
- Build the word letter by letter as you move through the cells
- Each cell can only be used once per word (you cannot revisit a cell while forming a single word)
The goal is to return a list containing all words from the input list that can be successfully formed on the board following these rules.
For example, if you have a board like:
[['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v']]
And words list: ["oath","pea","eat","rain"]
You could form "oath" by starting at board[0][0]
and moving right through the cells. You could form "eat" by starting at board[1][0]
and moving right then up. The word "rain" cannot be formed because although all letters exist, they're not connected in a valid path.
The solution uses a Trie data structure to efficiently store and search for all words simultaneously as we explore the board, combined with depth-first search (DFS) to explore all possible paths from each starting position. The board cells are temporarily marked with '#' during exploration to prevent revisiting the same cell within a single word search.
Flowchart Walkthrough
First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- No: While the board has a grid structure, this problem is not about traditional graph traversal with explicit nodes and edges. We're searching for word patterns on a 2D board.
Need to solve for kth smallest/largest?
- No: We're not looking for the kth smallest or largest element. We need to find all valid words from a given list.
Involves Linked Lists?
- No: The problem uses a 2D array/board, not linked lists.
Does the problem have small constraints?
- Yes: The problem has relatively small constraints:
- Board dimensions:
m x n
where typically both m and n are small (often ≤ 12) - Word length is limited (typically ≤ 10)
- The search space, while exponential, is manageable due to these constraints
- Board dimensions:
Brute force / Backtracking?
- Yes: This is a classic backtracking problem where we:
- Try each cell as a starting point
- Explore all possible paths from that cell
- Mark cells as visited during exploration
- Backtrack (unmark cells) when we finish exploring a path
- Need to explore all possibilities to find all valid words
Conclusion: The flowchart correctly leads us to use a Backtracking approach. The solution implements this by using DFS with backtracking, temporarily marking visited cells with '#' and restoring them after exploration. The Trie optimization helps efficiently check multiple words simultaneously during the backtracking process.
Intuition
When we need to find multiple words on a board, the naive approach would be to search for each word independently - for every word, try every cell as a starting point and explore all paths. However, this becomes inefficient when we have many words to search for, as we'd be traversing the same paths multiple times.
The key insight is that many words might share common prefixes. For example, if we're searching for "oath" and "oat", they share the prefix "oa". Instead of searching for these separately, we can search for all words simultaneously in a single traversal.
This leads us to the Trie (prefix tree) data structure. A Trie allows us to:
- Store all words in a tree structure where common prefixes are shared
- Check if our current path matches any word prefix in O(1) time per character
- Know immediately if we should continue exploring a path (if it matches a prefix) or abandon it (if no words have this prefix)
The backtracking aspect comes from the constraint that each cell can only be used once per word. As we explore paths:
- We mark the current cell as visited (using '#' in this solution)
- Recursively explore all four adjacent cells
- After exploring, we restore the original character (backtrack) so the cell can be used in other word searches
By combining Trie with DFS backtracking, we achieve an elegant solution where:
- We start DFS from every cell on the board
- At each step, we check if the current path exists in our Trie
- If we reach a complete word in the Trie, we add it to our results
- We prune paths early if they don't match any prefix in our Trie
- We ensure each cell is used only once per path through backtracking
This approach is much more efficient than searching for each word independently, especially when words share common prefixes or when we have many words to search for.
Solution Approach
The solution implements a Trie-based approach with DFS backtracking. Let's walk through the implementation step by step:
1. Building the Trie Data Structure
The Trie
class stores our word dictionary:
children
: An array of 26 elements (for 'a' to 'z'), where each element can be another Trie node orNone
ref
: Stores the index of the word in the original word list (-1 if this node doesn't represent a complete word)
The insert
method adds a word to the Trie:
def insert(self, w: str, ref: int):
node = self
for c in w:
idx = ord(c) - ord('a') # Convert character to index (0-25)
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.ref = ref # Mark the end of word with its index
2. DFS with Backtracking
The dfs
function explores paths on the board:
def dfs(node: Trie, i: int, j: int):
idx = ord(board[i][j]) - ord('a')
if node.children[idx] is None:
return # No words with this prefix, prune the search
node = node.children[idx]
if node.ref >= 0: # Found a complete word
ans.append(words[node.ref])
node.ref = -1 # Mark as found to avoid duplicates
3. Backtracking Mechanism
To ensure each cell is used only once per word:
c = board[i][j] board[i][j] = '#' # Mark cell as visited for a, b in pairwise((-1, 0, 1, 0, -1)): # Explore 4 directions x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and board[x][y] != '#': dfs(node, x, y) board[i][j] = c # Restore original character (backtrack)
The pairwise
function generates direction pairs: (-1,0)
, (0,1)
, (1,0)
, (0,-1)
for up, right, down, left movements.
4. Main Algorithm Flow
# Build Trie from all words
tree = Trie()
for i, w in enumerate(words):
tree.insert(w, i)
# Try starting from every cell
m, n = len(board), len(board[0])
ans = []
for i in range(m):
for j in range(n):
dfs(tree, i, j)
return ans
Key Optimizations:
- Early Pruning: If a path doesn't match any prefix in the Trie, we stop exploring
- Duplicate Prevention: Once a word is found, we set its
ref
to -1 to avoid adding it multiple times - In-place Marking: Instead of using a separate visited array, we temporarily modify the board itself
Time Complexity: O(m × n × 4^L) where m×n is the board size and L is the maximum word length Space Complexity: O(N × K) for the Trie, where N is the number of words and K is the average word length
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Given:
- Board:
[['a','b'], ['c','d']]
- Words:
["ab", "ac", "acd", "ba", "bd"]
Step 1: Build the Trie
We construct a Trie from our word list. The structure looks like:
root ├── a (ref=-1) │ ├── b (ref=0, word="ab") │ └── c (ref=1, word="ac") │ └── d (ref=2, word="acd") └── b (ref=-1) ├── a (ref=3, word="ba") └── d (ref=4, word="bd")
Step 2: Start DFS from board[0][0] = 'a'
- Check if 'a' exists in Trie → Yes, continue
- Mark cell (0,0) as visited:
board[0][0] = '#'
- Explore neighbors:
- Right to (0,1): 'b'
- Path "ab" exists in Trie and is a complete word → Add "ab" to results
- No further paths from 'b' under 'a'
- Down to (1,0): 'c'
- Path "ac" exists in Trie and is a complete word → Add "ac" to results
- Continue to explore from 'c'
- Right to (1,1): 'd'
- Path "acd" exists in Trie and is a complete word → Add "acd" to results
- Backtrack from 'd':
board[1][1] = 'd'
- Backtrack from 'c':
board[1][0] = 'c'
- Right to (0,1): 'b'
- Backtrack from 'a':
board[0][0] = 'a'
Step 3: Start DFS from board[0][1] = 'b'
- Check if 'b' exists in Trie → Yes, continue
- Mark cell (0,1) as visited:
board[0][1] = '#'
- Explore neighbors:
- Left to (0,0): 'a'
- Path "ba" exists in Trie and is a complete word → Add "ba" to results
- Down to (1,1): 'd'
- Path "bd" exists in Trie and is a complete word → Add "bd" to results
- Left to (0,0): 'a'
- Backtrack from 'b':
board[0][1] = 'b'
Step 4: Start DFS from board[1][0] = 'c' and board[1][1] = 'd'
Neither 'c' nor 'd' exist as starting characters in our Trie, so these searches are pruned immediately.
Final Result: ["ab", "ac", "acd", "ba", "bd"]
The key insights from this walkthrough:
- The Trie allows us to check all words simultaneously in a single traversal
- Backtracking (marking with '#' and restoring) ensures each cell is used only once per word
- Early pruning happens when a path doesn't match any prefix (like starting with 'c' or 'd')
- Each word is found exactly once due to marking
ref = -1
after finding
Solution Implementation
1from typing import List, Optional
2
3class TrieNode:
4 def __init__(self):
5 # Array to store references to child nodes (26 letters a-z)
6 self.children: List[Optional['TrieNode']] = [None] * 26
7 # Index reference to the word in the original words list (-1 means no word ends here)
8 self.word_index: int = -1
9
10 def insert(self, word: str, index: int) -> None:
11 """Insert a word into the trie with its index reference"""
12 current_node = self
13 for char in word:
14 # Calculate the index for this character (0-25)
15 char_index = ord(char) - ord('a')
16 # Create new node if path doesn't exist
17 if current_node.children[char_index] is None:
18 current_node.children[char_index] = TrieNode()
19 # Move to the child node
20 current_node = current_node.children[char_index]
21 # Mark the end of word with its index in the words list
22 current_node.word_index = index
23
24
25class Solution:
26 def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
27 def dfs(node: TrieNode, row: int, col: int) -> None:
28 """Depth-first search to find words in the board"""
29 # Get the character at current position
30 char_index = ord(board[row][col]) - ord('a')
31
32 # If no child exists for this character, stop exploring
33 if node.children[char_index] is None:
34 return
35
36 # Move to the child node
37 node = node.children[char_index]
38
39 # If we found a complete word, add it to results
40 if node.word_index >= 0:
41 result.append(words[node.word_index])
42 # Mark as visited to avoid duplicates
43 node.word_index = -1
44
45 # Temporarily mark current cell as visited
46 original_char = board[row][col]
47 board[row][col] = '#'
48
49 # Explore all four directions (up, right, down, left)
50 directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
51 for delta_row, delta_col in directions:
52 new_row, new_col = row + delta_row, col + delta_col
53 # Check if the new position is valid and not visited
54 if (0 <= new_row < rows and
55 0 <= new_col < cols and
56 board[new_row][new_col] != '#'):
57 dfs(node, new_row, new_col)
58
59 # Restore the original character
60 board[row][col] = original_char
61
62 # Build the trie from all words
63 trie_root = TrieNode()
64 for index, word in enumerate(words):
65 trie_root.insert(word, index)
66
67 # Initialize board dimensions and result list
68 rows, cols = len(board), len(board[0])
69 result = []
70
71 # Start DFS from each cell in the board
72 for row in range(rows):
73 for col in range(cols):
74 dfs(trie_root, row, col)
75
76 return result
77
1/**
2 * Trie (Prefix Tree) data structure for efficient word searching
3 */
4class Trie {
5 // Array to store 26 child nodes (one for each lowercase letter)
6 Trie[] children = new Trie[26];
7 // Index reference to the word in the words array (-1 means no word ends here)
8 int wordIndex = -1;
9
10 /**
11 * Inserts a word into the trie with its corresponding index
12 * @param word - the word to insert
13 * @param index - the index of the word in the words array
14 */
15 public void insert(String word, int index) {
16 Trie currentNode = this;
17
18 // Traverse through each character of the word
19 for (int i = 0; i < word.length(); i++) {
20 // Calculate the index for the character (0-25 for 'a'-'z')
21 int charIndex = word.charAt(i) - 'a';
22
23 // Create a new node if it doesn't exist
24 if (currentNode.children[charIndex] == null) {
25 currentNode.children[charIndex] = new Trie();
26 }
27
28 // Move to the child node
29 currentNode = currentNode.children[charIndex];
30 }
31
32 // Mark the end of the word with its index
33 currentNode.wordIndex = index;
34 }
35}
36
37/**
38 * Solution class to find all words from a list that exist in a 2D board
39 */
40class Solution {
41 private char[][] board;
42 private String[] words;
43 private List<String> result = new ArrayList<>();
44
45 /**
46 * Finds all words from the words array that can be formed in the board
47 * @param board - 2D character grid
48 * @param words - array of words to search for
49 * @return list of found words
50 */
51 public List<String> findWords(char[][] board, String[] words) {
52 this.board = board;
53 this.words = words;
54
55 // Build the trie with all words
56 Trie trieRoot = new Trie();
57 for (int i = 0; i < words.length; i++) {
58 trieRoot.insert(words[i], i);
59 }
60
61 int rows = board.length;
62 int cols = board[0].length;
63
64 // Start DFS from each cell in the board
65 for (int row = 0; row < rows; row++) {
66 for (int col = 0; col < cols; col++) {
67 dfs(trieRoot, row, col);
68 }
69 }
70
71 return result;
72 }
73
74 /**
75 * Depth-first search to find words starting from current position
76 * @param currentNode - current trie node
77 * @param row - current row position in board
78 * @param col - current column position in board
79 */
80 private void dfs(Trie currentNode, int row, int col) {
81 // Get the character index for the current board position
82 int charIndex = board[row][col] - 'a';
83
84 // If no child exists for this character, return
85 if (currentNode.children[charIndex] == null) {
86 return;
87 }
88
89 // Move to the child node
90 currentNode = currentNode.children[charIndex];
91
92 // If a word ends at this node, add it to results
93 if (currentNode.wordIndex != -1) {
94 result.add(words[currentNode.wordIndex]);
95 // Mark as visited to avoid duplicates
96 currentNode.wordIndex = -1;
97 }
98
99 // Mark current cell as visited
100 char originalChar = board[row][col];
101 board[row][col] = '#';
102
103 // Direction vectors for up, right, down, left movement
104 int[] directions = {-1, 0, 1, 0, -1};
105
106 // Explore all four adjacent cells
107 for (int k = 0; k < 4; k++) {
108 int newRow = row + directions[k];
109 int newCol = col + directions[k + 1];
110
111 // Check if the new position is valid and not visited
112 if (newRow >= 0 && newRow < board.length &&
113 newCol >= 0 && newCol < board[0].length &&
114 board[newRow][newCol] != '#') {
115 dfs(currentNode, newRow, newCol);
116 }
117 }
118
119 // Restore the original character (backtrack)
120 board[row][col] = originalChar;
121 }
122}
123
1class Trie {
2public:
3 vector<Trie*> children; // Array of 26 pointers for each lowercase letter
4 int wordIndex; // Index of word in the original words array (-1 if not a word end)
5
6 Trie() : children(26, nullptr), wordIndex(-1) {}
7
8 // Insert a word into the trie with its index in the words array
9 void insert(const string& word, int index) {
10 Trie* currentNode = this;
11 for (char ch : word) {
12 int charIndex = ch - 'a'; // Convert character to index (0-25)
13 if (!currentNode->children[charIndex]) {
14 currentNode->children[charIndex] = new Trie();
15 }
16 currentNode = currentNode->children[charIndex];
17 }
18 currentNode->wordIndex = index; // Mark the end of word with its index
19 }
20};
21
22class Solution {
23public:
24 vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
25 // Build trie from all words
26 Trie* root = new Trie();
27 for (int i = 0; i < words.size(); ++i) {
28 root->insert(words[i], i);
29 }
30
31 vector<string> result;
32 int rows = board.size();
33 int cols = board[0].size();
34
35 // DFS function to search words in the board
36 function<void(Trie*, int, int)> dfs = [&](Trie* node, int row, int col) {
37 char currentChar = board[row][col];
38 int charIndex = currentChar - 'a';
39
40 // If current character doesn't exist in trie, return
41 if (!node->children[charIndex]) {
42 return;
43 }
44
45 // Move to the child node
46 node = node->children[charIndex];
47
48 // If we found a complete word, add it to result
49 if (node->wordIndex != -1) {
50 result.emplace_back(words[node->wordIndex]);
51 node->wordIndex = -1; // Mark as visited to avoid duplicates
52 }
53
54 // Directions for exploring neighbors (up, right, down, left)
55 int directions[5] = {-1, 0, 1, 0, -1};
56
57 // Mark current cell as visited
58 board[row][col] = '#';
59
60 // Explore all four adjacent cells
61 for (int k = 0; k < 4; ++k) {
62 int newRow = row + directions[k];
63 int newCol = col + directions[k + 1];
64
65 // Check if the new position is valid and not visited
66 if (newRow >= 0 && newRow < rows &&
67 newCol >= 0 && newCol < cols &&
68 board[newRow][newCol] != '#') {
69 dfs(node, newRow, newCol);
70 }
71 }
72
73 // Restore the original character (backtrack)
74 board[row][col] = currentChar;
75 };
76
77 // Start DFS from every cell in the board
78 for (int i = 0; i < rows; ++i) {
79 for (int j = 0; j < cols; ++j) {
80 dfs(root, i, j);
81 }
82 }
83
84 return result;
85 }
86};
87
1// Trie node structure for efficient word storage and retrieval
2interface TrieNode {
3 children: TrieNode[]; // Array of 26 children nodes (for each letter a-z)
4 ref: number; // Reference index to the word in the words array (-1 if not a word end)
5}
6
7// Create a new Trie node
8function createTrieNode(): TrieNode {
9 return {
10 children: new Array(26),
11 ref: -1
12 };
13}
14
15// Insert a word into the Trie with its reference index
16function insertWord(root: TrieNode, word: string, referenceIndex: number): void {
17 let currentNode = root;
18
19 // Traverse through each character in the word
20 for (let i = 0; i < word.length; i++) {
21 // Convert character to index (0-25 for a-z)
22 const charIndex = word.charCodeAt(i) - 97;
23
24 // Create new node if path doesn't exist
25 if (currentNode.children[charIndex] == null) {
26 currentNode.children[charIndex] = createTrieNode();
27 }
28
29 // Move to the next node
30 currentNode = currentNode.children[charIndex];
31 }
32
33 // Mark the end of word with its reference index
34 currentNode.ref = referenceIndex;
35}
36
37// Find all words from the dictionary that exist in the board
38function findWords(board: string[][], words: string[]): string[] {
39 // Build Trie from all words
40 const trieRoot = createTrieNode();
41 for (let i = 0; i < words.length; i++) {
42 insertWord(trieRoot, words[i], i);
43 }
44
45 const rows = board.length;
46 const cols = board[0].length;
47 const result: string[] = [];
48
49 // Direction vectors for moving up, right, down, left
50 const directions = [-1, 0, 1, 0, -1];
51
52 // DFS function to explore the board from current position
53 const dfs = (node: TrieNode, row: number, col: number): void => {
54 // Get the character index for current board position
55 const charIndex = board[row][col].charCodeAt(0) - 97;
56
57 // If no child exists for this character, return
58 if (node.children[charIndex] == null) {
59 return;
60 }
61
62 // Move to the child node
63 node = node.children[charIndex];
64
65 // If current node marks end of a word, add it to result
66 if (node.ref !== -1) {
67 result.push(words[node.ref]);
68 node.ref = -1; // Mark as visited to avoid duplicates
69 }
70
71 // Temporarily mark current cell as visited
72 const originalChar = board[row][col];
73 board[row][col] = '#';
74
75 // Explore all four directions
76 for (let k = 0; k < 4; k++) {
77 const nextRow = row + directions[k];
78 const nextCol = col + directions[k + 1];
79
80 // Check if next position is valid and not visited
81 if (nextRow >= 0 && nextRow < rows &&
82 nextCol >= 0 && nextCol < cols &&
83 board[nextRow][nextCol] !== '#') {
84 dfs(node, nextRow, nextCol);
85 }
86 }
87
88 // Restore original character (backtrack)
89 board[row][col] = originalChar;
90 };
91
92 // Start DFS from every cell in the board
93 for (let i = 0; i < rows; i++) {
94 for (let j = 0; j < cols; j++) {
95 dfs(trieRoot, i, j);
96 }
97 }
98
99 return result;
100}
101
Time and Space Complexity
Time Complexity: O(M * N * 4^L + W * L)
where:
M * N
is the size of the board (M rows, N columns)L
is the maximum length of words in the word listW
is the number of words in the word list- The
W * L
term comes from building the Trie (inserting W words, each of length up to L) - The
M * N * 4^L
term represents the worst-case DFS exploration:- We start DFS from each of the
M * N
cells - From each cell, we can explore up to 4 directions
- The maximum depth of exploration is
L
(length of the longest word) - In the worst case, we might explore
4^L
paths (though pruning and visited marking reduce this significantly in practice)
- We start DFS from each of the
Space Complexity: O(W * L + L)
where:
W * L
space is used for the Trie structure:- In the worst case with no common prefixes, we store all characters of all words
- Each Trie node contains an array of 26 pointers plus an integer reference
L
additional space is used for the recursion call stack (maximum depth is the length of the longest word)- The
ans
list usesO(W)
space in the worst case if all words are found - The board modifications are done in-place, so no additional space is needed for tracking visited cells
Common Pitfalls
1. Not Handling Duplicate Words in Results
One of the most common mistakes is adding the same word multiple times to the result list when it can be formed from different starting positions or paths on the board.
The Problem:
# Incorrect approach - doesn't prevent duplicates if node.word_index >= 0: result.append(words[node.word_index]) # Forgetting to mark the word as found
If the word "eat" can be formed from multiple paths on the board, it would be added to the result list multiple times.
The Solution:
if node.word_index >= 0: result.append(words[node.word_index]) node.word_index = -1 # Mark as found to prevent duplicates
By setting word_index
to -1 after finding a word, we ensure that even if we encounter the same word endpoint again through a different path, it won't be added to the results.
2. Incorrect Backtracking - Not Restoring the Board State
Another critical mistake is forgetting to restore the board cell after exploring all paths from that cell.
The Problem:
# Incorrect - permanently modifying the board board[row][col] = '#' for delta_row, delta_col in directions: # ... explore neighbors ... # Forgot to restore board[row][col]!
This would permanently mark cells as visited, preventing them from being used in subsequent searches from other starting positions.
The Solution:
original_char = board[row][col] board[row][col] = '#' # Temporarily mark as visited # ... explore all directions ... board[row][col] = original_char # Always restore the original character
3. Memory Leak with Trie Nodes
When dealing with multiple test cases or large word lists, not properly managing the Trie can lead to memory issues.
The Problem: Not removing words from the Trie after finding them, especially when dealing with a large number of words that share prefixes.
The Solution: Consider implementing a cleanup mechanism that removes unnecessary Trie nodes:
def dfs(node: TrieNode, row: int, col: int) -> None:
# ... existing code ...
if node.word_index >= 0:
result.append(words[node.word_index])
node.word_index = -1
# Optional: Prune the trie if this branch has no more words
if not any(node.children) and node.word_index == -1:
# This node can be removed (implement parent tracking for this)
pass
4. Index Out of Bounds When Creating Character Index
The Problem:
char_index = ord(char) - ord('a') # Assumes all characters are lowercase
If the board contains uppercase letters or non-alphabetic characters, this will cause incorrect indexing or crashes.
The Solution: Add validation or normalization:
def insert(self, word: str, index: int) -> None:
current_node = self
for char in word:
if not 'a' <= char <= 'z':
return # Skip invalid characters or handle appropriately
char_index = ord(char) - ord('a')
# ... rest of the code
Or normalize input in the main function:
# Normalize board to lowercase if needed board = [[cell.lower() for cell in row] for row in board] words = [word.lower() for word in words]
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Want a Structured Path to Master System Design Too? Don’t Miss This!