跳到主要内容

LeetCode 212. 单词搜索 II

本节目标

用 Trie 合并候选词的共享前缀，在一次网格回溯中匹配多个单词。

这道题把搜索与剪枝综合中的网格回溯与前缀索引组合起来：搜索路径仍来自棋盘，但“这条前缀是否还有希望”由 Trie 统一回答。

查看 LeetCode 原题

题意与约束​

给定字符网格和一组互不相同的单词，返回所有能由网格相邻格子组成的单词。路径只能上下左右移动，同一个格子在一条路径中不能重复使用。

与单词搜索相比，棋盘规则没有变化，变化在于目标从一个单词变成一组单词。

朴素思路与瓶颈​

最直接的方法是对每个候选词单独执行一次完整网格 DFS。这能复用单词搜索的代码，却无法复用不同单词之间的共同工作。

例如 oa、oat、oath 共享前缀。分别搜索时，从字符 o 开始的相同路径会被重复走三次。候选词越多、共享前缀越长，浪费越明显。

让搜索路径沿 Trie 前进​

先用实现 Trie（前缀树）的方法把全部单词插入同一棵 Trie。根到节点的路径表示仍可能匹配的前缀，终止信息保存到达该节点时命中的完整单词；更系统的前缀结构可回顾匹配与字典树。

从每个网格位置开始 DFS 时，同时携带当前 Trie 节点：

  1. 当前字符不是该节点的子边，立即停止；这会一次排除所有不具有此前缀的单词。
  2. 子节点保存完整单词，说明当前路径命中答案。
  3. 临时把当前格标记为已使用，向四个方向继续。
  4. 返回前恢复字符，供其他起点或路径使用。

同一个单词可能由多条网格路径得到。命中后清除 Trie 节点上的终止信息，就能保证答案只加入一次；前缀节点仍被保留，因此不会影响更长单词。

这里不为每个候选词单独搜索，也不引入 AC 自动机。Trie 与网格回溯已经准确对应本题的重复结构和备考难度。

代码实现​

C++ Trie 使用节点数组和整数下标，避免容器扩容后保存悬空指针；Python 使用字符到节点的映射。两种实现都会恢复棋盘，并在一次调用期间安全保存 Trie。

C++17
#include <array>
#include <string>
#include <vector>

using namespace std;

class Solution {
private:
    struct TrieNode {
        array<int, 26> children{};
        string word;

        TrieNode() {
            children.fill(-1);
        }
    };

    vector<TrieNode> trie;
    vector<string> answer;
    int rows = 0;
    int cols = 0;

    void insert(const string& word) {
        int node = 0;
        for (char letter : word) {
            const int child = letter - 'a';
            if (trie[node].children[child] == -1) {
                trie[node].children[child] = static_cast<int>(trie.size());
                trie.emplace_back();
            }
            node = trie[node].children[child];
        }
        trie[node].word = word;
    }

    void dfs(vector<vector<char>>& board, int row, int col, int node) {
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            return;
        }

        const char letter = board[row][col];
        if (letter == '#') {
            return;
        }
        const int next = trie[node].children[letter - 'a'];
        if (next == -1) {
            return;
        }

        if (!trie[next].word.empty()) {
            answer.push_back(trie[next].word);
            trie[next].word.clear();
        }

        board[row][col] = '#';
        dfs(board, row - 1, col, next);
        dfs(board, row + 1, col, next);
        dfs(board, row, col - 1, next);
        dfs(board, row, col + 1, next);
        board[row][col] = letter;
    }

public:
    vector<string> findWords(
        vector<vector<char>>& board,
        vector<string>& words
    ) {
        trie.clear();
        trie.emplace_back();
        answer.clear();
        for (const string& word : words) {
            insert(word);
        }

        rows = static_cast<int>(board.size());
        cols = rows == 0 ? 0 : static_cast<int>(board[0].size());
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                dfs(board, row, col, 0);
            }
        }
        return answer;
    }
};

复杂度分析​

设网格大小为 M × N，所有单词字符总数为 S，最长单词长度为 L。

  • 建立 Trie 需要 O(S) 时间和空间。
  • 搜索的粗略上界为 O(MN · 4^L)；Trie 会在前缀不存在时提前终止，实际工作通常远小于逐词搜索。
  • 递归栈最多为 O(L)，Trie 占用 O(S) 空间；网格访问标记原地完成。

易错点​

  • 对每个单词单独运行网格搜索，重复遍历共享前缀。
  • 命中单词后直接返回，漏掉以它为前缀的更长单词。
  • 不清除终止信息，使同一个单词因多条路径被重复加入。
  • 回溯后没有恢复网格字符。
  • 在 C++ 中保存 vector 元素指针，扩容后继续使用失效地址。

模式迁移​

当“许多目标共享前缀”与“路径搜索”同时出现时，可以让 DFS 状态携带 Trie 节点，把候选集合随路径一起收缩。这个模式还能用于词典拼图和前缀约束枚举；多模式自动机、后缀结构等更复杂工具留给算法进阶。