Word Search II

Problem

Given a 2-D grid of characters board and a list of strings words, return all words that are present in the grid.

For a word to be present it must be possible to form the word with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.

Examples

Example 1:

Input:
board = [
  ["a","b","c","d"],
  ["s","a","a","t"],
  ["a","c","k","e"],
  ["a","c","d","n"]
],
words = ["bat","cat","back","backend","stack"]

Output: ["cat","back","backend"]

Example 2:

Input:
board = [
  ["x","o"],
  ["x","o"]
],
words = ["xoxo"]

Output: []

Constraints

• 1 <= board.length, board[i].length <= 12
• board[i] consists only of lowercase English letter.
• 1 <= words.length <= 30,000
• 1 <= words[i].length <= 10
• words[i] consists only of lowercase English letters.
• All strings within words are distinct.

You should aim for a solution with O(m * n * 4 * (3^(t-1)) + s) time and O(s) space, where m is the number of rows, n is the number of columns, t is the maximum length of any word and s is the sum of the lengths of all the words

Solution

The DFS find a word starting at the initial row/col and adds it to the set of found. A word is found if the node ends in a word. As we perform DFS, we can check the Trie if we are still on track to find a word.

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool end_of_word = false;
    TrieNode() = default;
    ~TrieNode() { 
        for (auto &&[_, child] : children) {
            delete child;
        }
    }
};
 
class Solution {
    TrieNode *root;
 
    void add_word(const auto &word) {
        TrieNode *current = root;
        for (const auto &c : word) {
            if (!current->children.contains(c)) {
                current->children[c] = new TrieNode();
            }
            current = current->children[c];
        }
        current->end_of_word = true;
    }
 
public:
    Solution() { root = new TrieNode(); }
    ~Solution() { delete root; }
 
    vector<string> findWords(const vector<vector<char>>& board, const vector<string>& words) {
        // Create tree
        for (const auto &word : words) {
            add_word(word);
        }
 
        int ROWS = board.size();
        int COLS = board[0].size();
        std::unordered_set<string> result;
        std::vector<bool> visited(ROWS*COLS, false);
 
        std::function<void(int, int, TrieNode*, std::string)> dfs;
        dfs = [&](int r, int c, TrieNode *node, std::string word) {
            // Out of bounds
            if (r < 0 || c < 0 || r >= ROWS || c >= COLS) {
                return;
            }
            // Previously visited
            if (visited[r*COLS + c]) { return; }
            // Current path does not form a word
            if (!node->children.contains(board[r][c])) {
                return;
            }
            // This cell progresses a word, mark and continue
            word += board[r][c];
            node = node->children[board[r][c]];
            if (node->end_of_word) {
                result.insert(word);
            }
 
            visited[r*COLS + c] = true;
            dfs(r-1, c, node, word);
            dfs(r+1, c, node, word);
            dfs(r, c-1, node, word);
            dfs(r, c+1, node, word);
            visited[r*COLS + c] = false;
        };
 
        for (int i = 0; i < ROWS; ++i) {
            for (int j = 0; j < COLS; ++j) {
                dfs(i, j, root, "");
            }
        }
        return std::vector<string>(result.begin(), result.end());
    }
};