Facebook Pixel

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

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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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:

  1. Store all words in a tree structure where common prefixes are shared
  2. Check if our current path matches any word prefix in O(1) time per character
  3. 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 or None
  • 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 Evaluator

Example 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'

  1. Check if 'a' exists in Trie → Yes, continue
  2. Mark cell (0,0) as visited: board[0][0] = '#'
  3. 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'
  4. Backtrack from 'a': board[0][0] = 'a'

Step 3: Start DFS from board[0][1] = 'b'

  1. Check if 'b' exists in Trie → Yes, continue
  2. Mark cell (0,1) as visited: board[0][1] = '#'
  3. 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
  4. 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 list
  • W 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)

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 uses O(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]
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More