LeetCode 212题单词搜索II回溯法超时（TLE）优化求助

嘿，我完全懂你现在的头疼——回溯逻辑明明是对的，但面对大数量的单词直接就超时了。其实核心问题出在你当前的搜索方式上，咱们一步步拆解优化点，把效率提上去！

首先得明确你现有代码的核心痛点：你是逐个单词去棋盘里做独立搜索，比如有3万个单词，每个单词都要从头扫一遍棋盘的每个格子，反复做相同前缀的回溯尝试（比如多个单词共享"oa"前缀，你的代码会重复搜N次这个前缀的路径），这冗余的计算量就是超时的元凶。

接下来给你几个针对性的优化方案，从核心思路到细节调整都覆盖到：

核心优化：用前缀树（Trie）批量处理所有单词 #

把所有单词先构建成一棵前缀树，然后从棋盘的每个格子出发，沿着前缀树的路径做回溯搜索。这样一来，所有共享前缀的单词都会被一次性处理，不用重复搜索相同的前缀路径，能大幅砍掉冗余操作。

具体步骤：

1. 定义Trie节点结构，每个节点包含26个小写字母的子节点指针，以及一个存储完整单词的字段（标记当前节点是否是某个单词的结尾）。
2. 把所有words里的单词插入到Trie中。
3. 从棋盘的每个格子出发，做深度优先搜索（回溯）：
   • 如果当前格子的字符不在Trie当前节点的子节点里，直接返回。
   • 如果当前节点是某个单词的结尾，把这个单词加入结果集（记得清空节点的单词字段，避免重复加入）。
   • 用修改棋盘字符的方式标记已访问（比如改成'#'，递归结束后再恢复），省掉单独的vis数组。
   • 递归搜索上下左右四个方向。
   • 恢复当前格子的原始字符。

细节优化：砍掉单独的vis数组 #

你现在用的vector<vector<bool>> vis完全可以省掉，直接在回溯时修改棋盘的字符：访问某个格子时，把它改成一个不在小写字母范围内的特殊字符（比如'#'），递归结束后再改回原始字符。这样既节省了内存，又减少了每次判断safe函数里!vis[i][j]的开销，速度能快一截。

额外剪枝技巧 #

• 一旦搜到某个单词，清空Trie节点对应的单词字段，避免后续重复搜到同一个单词。
• 如果当前Trie节点没有任何子节点了，可以直接终止回溯，因为没有更长的单词会从这里出发。

修改后的代码示例 #

下面是结合这些优化后的完整代码，你可以直接测试：

class Solution {
private:
    // 定义Trie节点结构
    struct TrieNode {
        TrieNode* children[26] = {nullptr};
        string word; // 存储当前节点对应的完整单词（仅当是单词结尾时非空）
    };

    // 向Trie中插入单词
    void insertWord(TrieNode* root, const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!curr->children[idx]) {
                curr->children[idx] = new TrieNode();
            }
            curr = curr->children[idx];
        }
        curr->word = word;
    }

    // 回溯搜索函数
    void backtrack(vector<vector<char>>& board, int i, int j, TrieNode* currNode, vector<string>& result) {
        char currChar = board[i][j];
        // 如果当前字符已被访问，或者不在Trie的当前路径中，直接返回
        if (currChar == '#' || !currNode->children[currChar - 'a']) {
            return;
        }

        currNode = currNode->children[currChar - 'a'];
        // 如果当前节点是某个单词的结尾，加入结果集并清空（避免重复）
        if (!currNode->word.empty()) {
            result.push_back(currNode->word);
            currNode->word.clear();
        }

        // 标记当前格子为已访问
        board[i][j] = '#';
        // 递归搜索上下左右四个方向
        if (i > 0) backtrack(board, i - 1, j, currNode, result);
        if (i < board.size() - 1) backtrack(board, i + 1, j, currNode, result);
        if (j > 0) backtrack(board, i, j - 1, currNode, result);
        if (j < board[0].size() - 1) backtrack(board, i, j + 1, currNode, result);
        // 恢复当前格子的原始字符
        board[i][j] = currChar;
    }

public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> result;
        // 构建前缀树
        TrieNode* root = new TrieNode();
        for (const string& word : words) {
            insertWord(root, word);
        }

        // 遍历棋盘每个格子，启动搜索
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                backtrack(board, i, j, root, result);
            }
        }

        // 可选：释放Trie内存（LeetCode环境下可以省略，程序结束后会自动回收）
        return result;
    }
};

为什么这个优化能解决超时？ #

原来的代码是单词驱动：每个单词独立搜索，重复前缀被多次遍历。而优化后的代码是棋盘驱动：从每个格子出发，沿着Trie路径一次性搜索所有可能的单词，共享前缀的路径只走一次，砍掉了90%以上的冗余计算。再加上去掉vis数组的细节优化，整体效率提升非常明显，面对3万单词的测试用例也能轻松通过。

你可以试试这个版本，应该能解决超时问题！

备注：内容来源于stack exchange，提问作者Divik