Word Search II
LeetCode Problem #212 (Hard)
Problem Statement
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cells, where "adjacent" cells are those horizontally or vertically neighbouring. The same letter cell may not be used more than once in a word.
Testcases
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: ["eat","oath"]Prerequisite Knowledge
Depth-First-Search
Refer to the Prerequisite Knowledge section in Surrounded Regions:
Surrounded RegionsTrie
A trie is an advanced data structure which is used to solve a very specific type of problem—representing and retrieving words.
In fact, the name "trie" is derived from the word "retrieve". The structure of a trie resembles that of a tree data structure, but for the purposes of distinction and avoiding confusion, "trie" is pronounced as "try".
A trie is unique in its ability to efficiently store and search for words that may be formed using the same prefixes.
In this tree, we can see that the words "that", "there", and "this" have the same prefix—"th". Instead of storing the letters of each word in separate spatial locations, the words are built based on pre-existing letters in the tree i.e. prefixes of existing words. For this reason, the trie data structure is also known as a "prefix tree".
Structure of a Trie
Each trie has a root node which is the starting point of the trie. The root node has links or references to every unique letter that can be possibly stored. Considering the English alphabet, this means that the root node can have 26 references or 26 child nodes from which words can be constructed.
However, other languages have alphabets of varying size, with some even having twice as many letters as the English alphabet or more. The size of the trie proportionally increases with the number of alphabetic values in the language being represented. This means that we might have to make a trade-off in terms of space complexity when we use tries, even if we benefit from the run-time efficiency.
References
For more information, detailed explanations, and notes on implementation refer to the links below:
Algorithm
Depth-First-Search Approach
In this approach, we use DFS to check the adjacent cells in the board to see if a word can be constructed using the letters in the cell. Although this approach does not require an extensive amount of space, it is very expensive in terms of execution time.
Identify the unique words from the given list of words using a set.
Iterate through each word in the list.
Check if the word exists on the board.
a. Iterate through each cell on the board.
b. Perform DFS from each letter to see if the word can be constructed.
DFS Helper Function
Mark the letters that have already been visited.
Iteratively check the adjacent nodes to see if a word can be constructed.
If the required word is found, return true. Otherwise, return false and check for other words.
Reference:
https://www.youtube.com/watch?v=aEEJ3xHIF5o&feature=emb_logo
Time Complexity: O(m*n*4^L)
Trie Approach
This is a significantly more efficient approach, albeit the compromise made in terms of space requirements. We construct a trie using the given list of words. DFS is performed only if there is an existing path indicated by a branch in the trie. If no path exists, we do not have to explore that particular branch.
Build the trie from the given list of words.
Iterate through each cell of the board using DFS and search for the letters needed to form a word.
Construct Word Function
Iterate through each letter of each word in the given list.
If the letter does not exist in the trie already, add it to the appropriate branch of the trie.
Store the letters and words in the trie structure.
DFS Helper Function
If the node has already been visited, return.
Recursively check each adjacent cell on the board to see if the letters will form a word from the given list.
Mark the node that has already been visited.
If a word has successfully been constructed, add it to the resultant vector.
Time Complexity: O(L+4^L)
Code
DFS Approach
int row;
int col;bool wordExists(vector<vector<char>>& board, string word) {
// There is no board
if(board.size() == 0) {
return false;
}
row = board.size();
col = board[0].size();
// Iterate through every cell in the board
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
// Perform DFS from each letter to see if the word can be constructed
if(DFS(board, word, 0, i, j)) {
return true;
}
}
}
return false;
}bool DFS(vector<vector<char>>& board, const string& word, int len, int i, int j) {
// Conditions to check if the current position is out of bounds
if(i < 0 || j < 0 || i == row || j == col || word[len] != board[i][j]) {
return false;
}
// The word has been found if the length of the word found is the same as the length of the word being searched
if(len == word.length() - 1) {
return true;
}
// Keep track of each letter that has been visited
char current_letter = board[i][j];
board[i][j] = 'X';
// DFS from each letter
// Return true if found and false if not found
bool found_letter = DFS(board, word, len + 1, i + 1, j)
|| DFS(board, word, len + 1, i - 1, j)
|| DFS(board, word, len + 1, i, j + 1)
|| DFS(board, word, len + 1, i, j - 1);
board[i][j] = current_letter;
return found_letter;
}vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
unordered_set<string> unique_words(words.begin(), words.end());
vector<string> words_found;
// Iterate through each word in the given word list
for(auto word : unique_words) {
// If the word is found, push it into the resultant vector
if(wordExists(board, word)) {
words_found.push_back(word);
}
}
return words_found;
}Trie Approach
struct TrieNode {
TrieNode* letter[26];
string word;
};TrieNode* constructWord(vector<string>& words) {
// Initialize the root node of the trie
TrieNode* root = new TrieNode();
// Iterate through each word in the list
for(int i = 0; i < words.size(); i++) {
string word = words[i];
TrieNode *node = root;
// Iterate through each letter of a word
for(int j = 0; j < word.size(); j++) {
char ch = word[j] - 'a';
// If the letter does not exist already, add it to the trie
if(node->letter[ch] == nullptr) {
node->letter[ch] = new TrieNode();
}
// Store the letter in the trie node
node = node->letter[ch];
}
// Store the word in the trie node
node->word = word;
}
return root;
}void search(vector<vector<char>>& board, TrieNode* node, int i, int j, vector<string>& words_found) {
// Check if the current position is out of bounds
if(i < 0 || j < 0 || i >= board.size() || j >= board[0].size()) {
return;
}
char current_letter = board[i][j];
char ch = current_letter - 'a';
// Check if the letter has already been visited
if(current_letter == 'X' || node->letter[ch] == nullptr) {
return;
}
node = node->letter[ch];
// Add the word found to the resultant array of words
if(node->word.size() > 0) {
words_found.push_back(node->word);
node->word = "";
}
// Mark visited nodes
board[i][j] = 'X';
// Perform DFS on each letter to check if it forms the given word
search(board, node, i + 1, j, words_found);
search(board, node, i, j + 1, words_found);
search(board, node, i - 1, j, words_found);
search(board, node, i, j - 1, words_found);
board[i][j] = current_letter;
}vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> words_found;
// Build the trie using the given list words
TrieNode* root = constructWord(words);
if(board.size() == 0) {
return words_found;
}
// Iterate through each cell of the board and search for the required letters to form a word
for(int i = 0; i < board.size(); i++) {
for(int j = 0; j < board[0].size(); j++) {
search(board, root, i, j, words_found);
}
}
return words_found;
}Last updated
Was this helpful?