【面试经典 150 | 字典树】单词搜索 II

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【字符串】【矩阵】【回溯】【字典树】

题目来源

212. 单词搜索 II

解题思路

在开始解题之前需要先掌握 208. 实现 Trie (前缀树)。

本题思路参考 官方题解。

方法一：回溯+字典树

思路

根据题意，我们需要逐个遍历二维网格中的每一个单元格，然后搜索从该单元格出发的所有路径，找出其中对应 words 中的单词路径。这是一个回溯的过程，具体步骤如下：

• 遍历二维网格中的每一个单元格。
• 从当前单元格开始向四周（上下左右四个方向）进行深搜。因为题目中要求每个单元格表示的字符在单词中只能出现一次，因此需要在深搜的时候将经过的单元格字符修改成特殊字符，以避免再次经过单元格。也可以使用一个布尔数组记录当前单元格是否被访问过。
• 如果当前路径是 words 中的单词，则将其加入结果数组中。
• 如果当前路径是 words 中任意一个单词的前缀，则继续搜素。反之，如果当前路径不是words 中任意一个单词的前缀，则剪枝。为此我们需要先将 words 中的所有字符串加到前缀树中，以方便深搜的时候查询。
• 在回溯的过程中，我们不需要每一步都判断完整的当前路径是否是 words 中任意一个单词的前缀；而是可以记录下路径中每个单元格所对应的前缀树结点，每次只需要判断新增单元格的字母是否是上一个单元格对应前缀树结点的子结点即可。

还需要注意：因为同一个单词可能在多个不同的路径中出现，所以我们需要使用哈希集合对结果集去重。

代码

class Solution {
private:
    const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    struct TrieNode {
        string word;    // 表示前缀树某条路径表示的字符串，只有到达某条路径结尾才会更新
        unordered_map<char, TrieNode*> chidren;
        TrieNode() {
            this->word = "";
        }
    };

    void insertTrie(TrieNode* root, const string& word) {
        TrieNode* node = root;
        for (auto c : word) {
            if (!node->chidren.count(c)) {
                node->chidren[c] = new TrieNode();
            }
            node = node->chidren[c];
        }
        node->word = word;
    }

    bool dfs(vector<vector<char>>& board, int x, int y, TrieNode* root, set<string>& res) {
        char ch = board[x][y];
        // 当前搜索到的字符不是上一个单元格对应前缀树结点的子结点
        if (!root->chidren.count(ch)) {
            return false;
        }
        root = root->chidren[ch];
        // 到达前缀树中某个单词的结尾了，因为只有到达时才会更新当前 root->word 为前缀树这条路径表示的字符串
        if (root->word.size() > 0) {    
            res.insert(root->word);
        }

        board[x][y] = '#';
        for (int i = 0; i < 4; ++i) {
            int nx = x + dirs[i][0];
            int ny = y + dirs[i][1];
            if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size() && board[nx][ny] != '#') {
                dfs(board, nx, ny, root, res);
            }
        }
        // 恢复现场
        board[x][y] = ch; 
        return true;
    }

public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        TrieNode* root = new TrieNode();
        set<string> res;
        vector<string> ans;

        for (auto& word : words) {
            insertTrie(root, word);
        }

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

        for (auto& word : res) {
            ans.emplace_back(word);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：$O(m\times n\times 3^{l-1})$，其中 $m$ 是二维网格的高度，$n$ 是二维网格的宽度，$l$ 是最长单词的长度。我们需要遍历 $m\times n$ 个单元格，每个单元格最多需要遍历 $4\times 3^{l-1}$ 条路径。

空间复杂度：$O(k\times l)$，其中 $k$ 是 words 的长度，$l$ 是最长单词的长度。最坏情况下，我们需要 $O(k\times l)$ 用于存储前缀树。

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。