【9.8】树结构-使用字典树解单词搜索 II

一、题目

        给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。

        单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例 1：

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

示例 2：

输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] 是一个小写英文字母
• 1 <= words.length <= 3 * 104
• 1 <= words[i].length <= 10
• words[i] 由小写英文字母组成
• words 中的所有字符串互不相同

二、解题思路

        除了回溯算法，我们还可以利用字典树来解决这个问题。具体的解题思路如下：首先，我们根据给定的字符串列表 `words` 构建一个字典树。接着，我们从二维数组中的每个字符出发，尝试在字典树中搜索是否存在完整的字符串。为了更直观地理解这个过程，我们可以通过示例一来绘制字典树的结构图。

        题目中明确指出，字符串仅由小写英文字母组成。由于小写英文字母总共有 26 个，因此我们可以将字典树视为一棵 26 叉树，其中每个节点最多可能包含 26 个子节点。

        在构建字典树时，每个节点都需要一个标识，用于表示从根节点到当前节点的路径是否构成一个完整的字符串。这个标识的具体形式可以根据需求灵活定义。为了方便后续的计算，这里我们采用一个字符串作为标识：如果该字符串为空，则表示从根节点到当前节点的路径不是一个完整的字符串；如果该字符串非空，则表示这条路径构成了一个完整的字符串。

三、代码实现

#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>

using namespace std;

// TrieNode 结构体定义
struct TrieNode {
    TrieNode* children[26];
    string word; // 用于标记从根节点到当前节点是否构成一个完整的单词
    TrieNode() {
        for (int i = 0; i < 26; ++i) {
            children[i] = nullptr;
        }
        word = "";
    }
};

// Trie 类定义
class Trie {
public:
    TrieNode* root;

    Trie() {
        root = new TrieNode();
    }

    // 插入单词到字典树
    void insert(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            int index = ch - 'a';
            if (node->children[index] == nullptr) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->word = word; // 标记完整单词
    }
};

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Trie trie;
        // 构建字典树
        for (const string& word : words) {
            trie.insert(word);
        }

        int wordLength = words.size();
        unordered_set<string> resultSet;

        // 遍历二维网格中的每个字符
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                dfs(board, trie.root, i, j, resultSet);
                // 如果找到所有单词，直接返回
                if (resultSet.size() == wordLength) {
                    return vector<string>(resultSet.begin(), resultSet.end());
                }
            }
        }

        return vector<string>(resultSet.begin(), resultSet.end());
    }

private:
    void dfs(vector<vector<char>>& board, TrieNode* node, int i, int j, unordered_set<string>& resultSet) {
        // 边界检查
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) {
            return;
        }

        // 如果当前字符已经被访问过，直接返回
        if (board[i][j] == '#') {
            return;
        }

        // 检查字典树中是否存在当前字符
        int index = board[i][j] - 'a';
        if (node == nullptr || node->children[index] == nullptr) {
            return;
        }

        node = node->children[index];
        // 如果当前节点是一个完整单词，加入结果集
        if (!node->word.empty()) {
            resultSet.insert(node->word);
        }

        // 标记当前字符为已访问
        char tmp = board[i][j];
        board[i][j] = '#';

        // 向四个方向递归搜索
        dfs(board, node, i - 1, j, resultSet); // 上
        dfs(board, node, i + 1, j, resultSet); // 下
        dfs(board, node, i, j - 1, resultSet); // 左
        dfs(board, node, i, j + 1, resultSet); // 右

        // 恢复当前字符
        board[i][j] = tmp;
    }
};

// 主函数
int main() {
    Solution solution;
    vector<vector<char>> board = {
        {'o', 'a', 'a', 'n'},
        {'e', 't', 'a', 'e'},
        {'i', 'h', 'k', 'r'},
        {'i', 'f', 'l', 'v'}
    };
    vector<string> words = {"oath", "pea", "eat", "rain"};

    vector<string> result = solution.findWords(board, words);

    // 输出结果
    cout << "Found words: ";
    for (const string& word : result) {
        cout << word << " ";
    }
    cout << endl;

    return 0;
}

        在最坏情况下，我们需要以矩阵中的每个位置作为起点进行搜索，因此这一部分的时间复杂度为 **O(M * N)**，其中 **M** 是矩阵的行数，**N** 是矩阵的列数。对于每个起点，DFS 会向四个方向递归搜索，但由于不能往回走（即不能重复访问已经访问过的节点），实际每次递归只有 **3 个有效方向**。因此，DFS 的时间复杂度为 **O(3^L)**，其中 **L** 是字符串列表 `words` 中最长字符串的长度。综合起来，算法的总时间复杂度为 **O(M * N * 3^L)**。