Leetcode Study Day 48

Word Search II

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a 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: ["eat","oath"]
Example 2:


Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
 

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] is a lowercase English letter.
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.

Solution

This question is like a combination of island question and prefix tree. Let’s explain the code line by line:

This C++ code defines a class Solution that implements a solution to the “Word Search II” problem using a Trie data structure and Depth-First Search (DFS). The problem involves finding all words from a given list that can be formed by sequentially adjacent letters on a board.

struct TrieNode {
    TrieNode *children[26];
    string word;

    TrieNode() : word("") {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

• This is a definition of a TrieNode structure. Each node has 26 children (one for each letter of the alphabet) and a string word. The constructor initializes word to an empty string and all children pointers to nullptr.

vector<string> findWords(vector<vector<char>> &board, vector<string> &words) {

• This function, findWords, is the main function of the class. It takes a 2D character vector board and a vector of strings words as input.

TrieNode *root = buildTrie(words);

• Here, a Trie is built from the list of words using the buildTrie function.

vector<string> result;

• This line initializes a vector result to store the words found on the board.

for (int i = 0; i < board.size(); i++) {
    for (int j = 0; j < board[0].size(); j++) {
        dfs(board, i, j, root, result);
    }
}

• These lines iterate over each cell of the board and call the dfs (Depth-First Search) function for each cell.

    return result;
}

• Returns the vector result containing all the words found on the board.

TrieNode *buildTrie(vector<string> &words) {

• This function, buildTrie, creates a Trie from the given list of words.

TrieNode *root = new TrieNode();

• Creates a new TrieNode that will serve as the root of the Trie.

for (int j = 0; j < words.size(); j++) {
    string word = words[j];
    TrieNode *curr = root;
    for (int i = 0; i < word.length(); i++) {
        char c = word[i] - 'a';
        if (curr->children[c] == nullptr) {
            curr->children[c] = new TrieNode();
        }
        curr = curr->children[c];
    }
    curr->word = word;
}

• This loop inserts each word into the Trie. For each character in a word, it checks if the corresponding child node exists; if not, it creates a new node. After inserting all characters of a word, it sets the word field of the last node.

    return root;
}

• Returns the root of the Trie.

void dfs(vector<vector<char>> &board, int i, int j, TrieNode *p, vector<string> &result) {

• This function, dfs, performs a depth-first search on the board starting from the cell (i, j).

char c = board[i][j];
if (c == '#' || !p->children[c - 'a']) return;

• This checks if the current cell is already visited (marked as ‘#’) or if there is no child in the Trie corresponding to the current character. If either is true, it returns immediately.

p = p->children[c - 'a'];

• Moves to the child node corresponding to the current character.

if (p->word.size() > 0) {
    result.push_back(p->word);
    p->word = "";
}

• If the current Trie node has a word (i.e., we have found a word), it adds the word to the result and clears the word in the Trie node to avoid duplicates.

board[i][j] = '#';

• Marks the current cell as visited.

if (i > 0) dfs(board, i - 1, j, p, result);
if (j > 0) dfs(board, i, j - 1, p, result);
if (i < board.size() - 1) dfs(board, i + 1, j, p, result);
if (j < board[0].size() - 1) dfs(board, i, j + 1, p, result);

• These lines recursively call dfs for all four adjacent cells (up, left, down, right), if they are within the bounds of the board.

    board[i][j] = c;
}

• Restores the current cell’s original character (unmarking it as visited).

This code efficiently searches for words on a board using Trie and DFS, which is a great demonstration of your understanding of advanced data structures and algorithms.

How Word stored in Trie

In the given implementation of the Trie (prefix tree), the complete word is stored in the last node of its corresponding path. Here’s how it works:

1. Trie Structure: Each node in the Trie represents a single character. The root node typically represents an empty string, and each path from the root to a node represents a prefix of some word.

2. Storing Words: As you insert a word into the Trie, you create a path where each character of the word corresponds to a node. When you reach the end of the word, you store the entire word at the last node in this path.

3. Why Store the Whole Word: Storing the entire word at the last node is particularly useful for applications like the word search problem. When you traverse the Trie during the search, reaching a node with a non-empty word field immediately tells you that you’ve found a valid word. This approach eliminates the need to reconstruct the word from the path you’ve traversed.

4. Example: Suppose you insert the word “cat” into an empty Trie. You’ll create nodes for ‘c’, ‘a’, and ‘t’. At the ‘t’ node, you’ll store the entire word “cat”. If you later insert “car”, you’ll add an ‘r’ node after the ‘a’ node (which is shared with “cat”), and store “car” at the ‘r’ node.

This method is efficient for word search problems because it allows for quick and direct identification of complete words during the traversal of the Trie.

Full code

class Solution {
    struct TrieNode {
        TrieNode *children[26];
        string word;

        TrieNode() : word("") {
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
        }
    };

public:
    vector<string> findWords(vector<vector<char>> &board, vector<string> &words) {
        TrieNode *root = buildTrie(words);
        vector<string> result;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                dfs(board, i, j, root, result);
            }
        }
        return result;
    }

    /** Inserts a word into the trie. */
    TrieNode *buildTrie(vector<string> &words) {
        TrieNode *root = new TrieNode();
        for (int j = 0; j < words.size(); j++) {
            string word = words[j];
            TrieNode *curr = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word[i] - 'a';
                if (curr->children[c] == nullptr) {
                    curr->children[c] = new TrieNode();
                }
                curr = curr->children[c];
            }
            curr->word = word;
        }
        return root;
    }

    void dfs(vector<vector<char>> &board, int i, int j, TrieNode *p, vector<string> &result) {
        char c = board[i][j];
        if (c == '#' || !p->children[c - 'a']) return;
        p = p->children[c - 'a'];
        if (p->word.size() > 0) {
            result.push_back(p->word);
            p->word = "";
        }

        board[i][j] = '#';
        if (i > 0) dfs(board, i - 1, j, p, result);
        if (j > 0) dfs(board, i, j - 1, p, result);
        if (i < board.size() - 1) dfs(board, i + 1, j, p, result);
        if (j < board[0].size() - 1) dfs(board, i, j + 1, p, result);
        board[i][j] = c;
    }
};