Word Search II

Link

Description

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 * 10^4
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

Solution

Dynamic Array

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

    TrieNode() {
        memset(son, 0, sizeof(son));
    }
};

class Solution {
private:
    vector<vector<char>> board;
    vector<string> res;

    array<int, 4> dx{-1, 0, 1, 0};
    array<int, 4> dy{0, 1, 0, -1};

    void buildTrie(const vector<string>& words, TrieNode* root) {
        for (const string& word : words) {
            TrieNode* node = root;

            for (const char& ch : word) {
                int index = ch - 'a';
                if (!node->son[index]) {
                    node->son[index] = new TrieNode();
                }
                node = node->son[index];
            }

            node->word = word;
        }
    }

    void backtracking(int row, int col, TrieNode* parent) {
        char letter = board[row][col];
        int index = letter - 'a';
        TrieNode* current = parent->son[index];

        if (!current->word.empty()) {
            res.push_back(current->word);
            current->word.clear();
        }

        board[row][col] = '#';

        for (int i = 0; i < 4; i++) {
            int newRow = row + dx[i];
            int newCol = col + dy[i];
            if (newRow < 0 || newRow >= board.size() || newCol < 0 || newCol >= board[0].size()) {
                continue;
            }

            int newIndex = board[newRow][newCol] - 'a';
            if (newIndex >= 0 && current->son[newIndex]) {
                backtracking(newRow, newCol, current);
            }
        }

        board[row][col] = letter;

        bool hasSon = false;
        for (int i = 0; i < 26; i++) {
            if (current->son[i]) {
                hasSon = true;
                break;
            }
        }
        if (!hasSon) {
            delete current;
            parent->son[index] = nullptr;
        }
    }

public:
    vector<string> findWords(vector<vector<char>>& _board, vector<string>& words) {
        board = _board;

        TrieNode* root = new TrieNode();
        buildTrie(words, root);

        for (int row = 0; row < _board.size(); row++) {
            for (int col = 0; col < _board[0].size(); col++) {
                int index = _board[row][col] - 'a';
                if (root->son[index]) {
                    backtracking(row, col, root);
                }
            }
        }

        return res;
    }
};

Static Array

class Solution {
private:
    static const int N = 10010;
    int son[N][26] {0};
    int passing[N] {0};
    vector<string> ending;
    int cnt {1};

    void build(const vector<string>& words) {
        ending.resize(N);

        for (const string& word : words) {
            int current = 1;
            passing[current]++;
            for (const char& ch : word) {
                int index = ch - 'a';
                if (!son[current][index]) {
                    son[current][index] = ++cnt;
                }
                current = son[current][index];
                passing[current]++;
            }
            ending[current] = word;
        }
    }

    int backtracking(vector<vector<char>>& board, int i, int j, int t, vector<string>& res) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] == '#') {
            return 0;
        }

        char temp = board[i][j];
        int road = temp - 'a';
        t = son[t][road];

        if (!passing[t]) {
            return 0;
        }

        int fix = 0;
        if (ending[t] != "") {
            fix++;
            res.push_back(ending[t]);
            ending[t] = "";
        }

        board[i][j] = '#';
        fix += backtracking(board, i - 1, j, t, res);
        fix += backtracking(board, i + 1, j, t, res);
        fix += backtracking(board, i, j - 1, t, res);
        fix += backtracking(board, i, j + 1, t, res);
        passing[t] -= fix;
        board[i][j] = temp;

        return fix;
    }

public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        build(words);

        vector<string> res;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                backtracking(board, i, j, 1, res);
            }
        }

        return res;
    }
};

• Time complexity: \(O\left( MN\cdot 4\cdot 3^{L-1} \right)\), \(L=10\);
• Space complexity: \(O\left( \sum_{i=0}^{words.size\left( \right) -1}{words\left[ i \right] .length\left( \right) \times 26} \right)\).