Given a 2D board of characters and a list of words, return all words that can be formed on the board. Each word must be built by moving to horizontally or vertically adjacent cells. The same cell cannot be used more than once while forming one word.
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 words "oath" and "eat" can be formed by moving through adjacent cells. The words "pea" and "rain" cannot be formed on this board.
Example 2
Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
Explanation: The word "abcb" cannot be formed because the same cell cannot be used twice in one path.
Brute Force Approach
The most direct thought is to pick one word, try to build it on the board, and then repeat the same process for the next word. This is exactly how Word Search I is usually solved. Start from every cell, match characters one by one, and use backtracking so one path does not reuse the same cell. This approach is easy to understand, but it repeats a lot of work. If many words start with the same prefix like "oa" or "eat", the board keeps exploring similar paths again and again for different words.
Algorithm
Pick one word from the list and try to find it on the board. This is done because the brute force method treats every word as a separate search problem.
For that word, start DFS from every cell because the first character could begin anywhere on the board.
During DFS, stop immediately if the current cell goes out of bounds, is already used in the current path, or does not match the required character. This early stopping is needed so invalid paths do not waste extra recursion.
If all characters of the word are matched, return
truefor that word because a complete valid path has been found.While exploring a path, temporarily mark the current cell as visited so it cannot be reused in the same word, which follows the problem rule.
Explore the four directions: up, down, left, and right, because those are the only allowed adjacent moves.
After exploring, restore the cell so it can be used for other paths and other words. This backtracking step is necessary because one failed path should not block future searches.
Repeat the same search for every word and collect the words that are found, because the final answer needs every valid dictionary word present on the board.
Dry Run
Word Search 2 Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Checks whether the current word can be completed from this board cell. bool dfs(vector<vector<char>>& board, int row, int col, const string& word, int index) { // All characters are matched, so this word exists on the board. if (index == (int)word.size()) { return true; } // Invalid positions or wrong characters cannot continue the current path. if (row < 0 || row >= (int)board.size() || col < 0 || col >= (int)board[0].size() || board[row][col] != word[index]) { return false; } // Save the current cell before marking it as used in this path. char currentChar = board[row][col]; // Mark the cell so it is not reused in the same word. board[row][col] = '#'; bool found = dfs(board, row + 1, col, word, index + 1) || dfs(board, row - 1, col, word, index + 1) || dfs(board, row, col + 1, word, index + 1) || dfs(board, row, col - 1, word, index + 1); // Restore the original character for other paths. board[row][col] = currentChar; return found; } // Tries every board cell as a starting point for one word. bool exists(vector<vector<char>>& board, const string& word) { for (int row = 0; row < (int)board.size(); row++) { for (int col = 0; col < (int)board[0].size(); col++) { // Start searching only when the first character matches. if (board[row][col] == word[0] && dfs(board, row, col, word, 0)) { return true; } } } return false; }public: /* Returns all words that can be formed on the board by searching each word separately with DFS. */ vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { vector<string> answer; for (const string& word : words) { // Add the word only when it exists on the board. if (exists(board, word)) { answer.push_back(word); } } return answer; }};// Driver code startsint main() { vector<vector<char>> board = { {'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'} }; vector<string> words = {"oath", "pea", "eat", "rain"}; Solution obj; vector<string> result = obj.findWords(board, words); for (const string& word : result) { cout << word << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(W x M x N x 4 x 3(L - 1)), where W is the number of words, M x N is the board size, and L is the maximum word length. Each word may start from every cell and explore multiple paths.
Space Complexity: O(L), because the recursion stack can go as deep as the length of the current word.
Optimal Approach
The repeated work in the brute force method comes from searching the board separately for every word. But many words share prefixes. For example, "oat" and "oath" start the same way. If the board is already exploring a path that spells "oa", it would be nice if that one path could help check all words that begin with "oa" together. That is exactly where a Trie helps. Instead of asking, "Can this board path match this one word?", the Trie changes the question into, "Can this board path match any word prefix at all?" If the answer is no, that path stops immediately. If the answer is yes, the DFS keeps growing that path, and whenever a Trie node marks a full word, that word is added to the result.
Algorithm
Insert all words into a Trie so shared prefixes are stored only once. This is helpful because many words may begin with the same letters.
Start DFS from every cell of the board because any cell can begin a valid word.
At each step, check whether the current board character exists as a child of the current Trie node. This tells whether the current board path still matches at least one word prefix.
If that child does not exist, stop immediately because no word in the dictionary can continue from this path.
If the child exists, move to that Trie node and check whether it stores a complete word. This matters because a path can be both a useful prefix and a finished answer.
If a full word is found, add it to the answer and clear that stored word so the same result is not added again from another path.
Mark the current board cell as visited, explore the four directions, and then restore the character during backtracking. This is needed to obey the no-reuse rule while still allowing the cell to be used in later searches.
Continue until all board cells have been used as starting points, because any one of them could lead to a valid word.
Dry Run
Solution
Word Search 2 Optimal Dry Run
#include <bits/stdc++.h>using namespace std;class TrieNode {public: vector<TrieNode*> children; string word; TrieNode() { children.assign(26, nullptr); word = ""; }};class Solution {private: // Builds a trie from all words so DFS can prune invalid prefixes early. TrieNode* buildTrie(vector<string>& words) { TrieNode* root = new TrieNode(); for (const string& word : words) { TrieNode* node = root; for (char ch : word) { int index = ch - 'a'; // Create the next trie node only when this prefix appears for the first time. if (node->children[index] == nullptr) { node->children[index] = new TrieNode(); } node = node->children[index]; } // Store the full word at the end node so it can be added directly when found. node->word = word; } return root; } // Explores the board and trie together from one cell. void dfs(vector<vector<char>>& board, int row, int col, TrieNode* node, vector<string>& answer) { // Positions outside the board cannot continue the current path. if (row < 0 || row >= (int)board.size() || col < 0 || col >= (int)board[0].size()) { return; } char currentChar = board[row][col]; // A visited cell or missing trie branch means this path is no longer useful. if (currentChar == '#' || node->children[currentChar - 'a'] == nullptr) { return; } node = node->children[currentChar - 'a']; // Add the word once and clear it so duplicate paths do not add it again. if (node->word != "") { answer.push_back(node->word); node->word = ""; } // Mark the cell so the current path does not reuse it. board[row][col] = '#'; dfs(board, row + 1, col, node, answer); dfs(board, row - 1, col, node, answer); dfs(board, row, col + 1, node, answer); dfs(board, row, col - 1, node, answer); // Restore the cell for future paths. board[row][col] = currentChar; }public: /* Returns all words that can be formed on the board by searching the board and trie together. */ vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { TrieNode* root = buildTrie(words); vector<string> answer; // try checking for each starting box for (int row = 0; row < (int)board.size(); row++) { for (int col = 0; col < (int)board[0].size(); col++) { dfs(board, row, col, root, answer); } } return answer; }};// Driver code startsint main() { vector<vector<char>> board = { {'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'} }; vector<string> words = {"oath", "pea", "eat", "rain"}; Solution obj; vector<string> result = obj.findWords(board, words); for (const string& word : result) { cout << word << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: In the worst case, O(M x N x 4 x 3(L - 1) + S), where M x N is the board size, L is the maximum word length, and S is the total number of characters in all words inserted into the Trie. In practice, Trie pruning removes many useless searches early.
Space Complexity: O(S x 26 + L), where S is the total number of characters across all dictionary words. Each node in the Trie represents a character and statically allocates an array of 26 child pointers (for lowercase English letters) to store potential branch connections.
FAQs
Q1. Why is a Trie better than standard DFS for Word Search II?
Standard DFS searches the board separately for every word, causing massive redundant exploration when words share common prefixes (like "oat" and "oath"). A Trie combines all words into a single search structure, allowing DFS to search the board for all words simultaneously and prune invalid paths as soon as a prefix is not found.
Q2. Why is node->word cleared to an empty string once a word is found?
Multiple distinct paths on the board can form the exact same word. Clearing node->word = "" immediately after pushing it to the result array prevents the algorithm from adding duplicate copies of the same word if another valid path for that word is discovered later during the board traversal.
Q3. How does Trie pruning optimize the worst-case time complexity?
In standard backtracking, invalid paths continue exploring until they run out of word length or hit a board boundary. With Trie pruning, as soon as a board character does not match any valid child node in the Trie (node->children[ch - 'a'] == nullptr), the search backtracks instantly, skipping entire branches of invalid searches.
Q4. What is the space complexity contribution of the Trie structure in this problem?
The space complexity is O(S x 26), where S is the total number of characters across all dictionary words. Each node in the Trie represents a character and statically allocates an array of 26 child pointers (for lowercase English letters) to store potential branch connections.
Be the first to add a comment.