单词搜索 II

Leetcode题目链接

描述

详见中文题目链接。

解答

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