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.

Note:

1. All inputs are consist of lowercase letters a-z.

2. The values of words are distinct.

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 Regions

Trie

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.

Prefix Tree

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:

Trying to Understand TriesMedium

Tries · Data Structures

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.

1. Identify the unique words from the given list of words using a set.

2. Iterate through each word in the list.

3. 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

1. Mark the letters that have already been visited.

2. Iteratively check the adjacent nodes to see if a word can be constructed.

3. 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.

1. Build the trie from the given list of words.

2. Iterate through each cell of the board using DFS and search for the letters needed to form a word.

Construct Word Function

1. Iterate through each letter of each word in the given list.

2. If the letter does not exist in the trie already, add it to the appropriate branch of the trie.

3. Store the letters and words in the trie structure.

DFS Helper Function

1. If the node has already been visited, return.

2. Recursively check each adjacent cell on the board to see if the letters will form a word from the given list.

3. Mark the node that has already been visited.

4. If a word has successfully been constructed, add it to the resultant vector.

Time Complexity: O(L+4^L)

Code

DFS Approach

Global Variables

int row;
int col;

Word Exists Function

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;
}

DFS Helper Function

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;
}

Find Words Function

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

TrieNode Structure

struct TrieNode {
    TrieNode* letter[26];
    string word;
};

Construct Word Function (Build Trie)

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;
}

DFS Helper Function

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;
}

Find Words Function

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;
}