在leetcode问题212-单词搜索2中使用backtrcaking获得TLE，即使在修剪之后，我如何进一步优化它[关闭]

Question

问题

给定一个

m x n

字符板和字符串单词列表，返回板上的所有单词。

每个单词必须由顺序相邻的单元格的字母构成，其中相邻的单元格水平或垂直相邻。同一字母单元不得在一个单词中使用多次。

限制：

• m == board.length

• n == board[i].length

• 1 <= m, n <= 12

• board[i][j]

  是一个小写英文字母。

• 1 <= words.length <= 3 * 10^4

• 1 <= words[i].length <= 10

• words[i]

  由小写英文字母组成。
• 所有字符串都是唯一的。

示例：

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h" ,"k","r"],["i","f","l","v"]], 单词 = ["誓言","豌豆","吃","雨"] 输出：[“吃”，“誓”]

class Solution {
private:
    bool safe(int i, int j, vector<vector<bool>> &vis) {
        return (i >= 0 && i < vis.size() && j >= 0 && j < vis[0].size() && !vis[i][j]);
    }
    void solve(vector<string> &ans, vector<vector<char>>& board, vector<vector<bool>> &vis, string &s,
    int row, int col, int idx, int &flag){
        if (!safe(row, col, vis) || board[row][col] != s[idx])
            return;
        if(idx+1==s.size()){
            flag=1;
            ans.push_back(s);
            return;
        }

        vis[row][col] = true;
        solve(ans, board,vis, s, row + 1, col, idx + 1,flag); 
        vis[row][col] = false; 
        if(flag==1) return;

        vis[row][col] = true; 
        solve(ans, board,vis, s, row - 1, col, idx + 1,flag); 
        vis[row][col] = false;
        if(flag==1) return;

        vis[row][col] = true; 
        solve(ans, board,vis, s, row, col + 1, idx + 1,flag); 
        vis[row][col] = false;
        if(flag==1) return;

        vis[row][col] = true; 
        solve(ans, board,vis, s, row, col - 1, idx + 1,flag); 
        vis[row][col] = false;
        if(flag==1) return;

        return;
    }
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> ans;
        vector<vector<bool>> vis(board.size(),vector<bool>(board[0].size(),0));
        for(int i=0;i<words.size();i++){
            int flag=0;
            for(int j=0;j<board.size();j++){
                for(int k=0;k<board[0].size();k++){
                    solve(ans,board,vis,words[i],j,k,0,flag);
                    if(flag==1) break;
                }
                if(flag==1) break;
            }
        }
        return ans;
    }
};

我正在使用问题标签指定的backtracking来做这个问题。虽然我的代码给出了正确的答案，但对于非常大的输入，它给出了TLE。 我已经尝试尽可能地优化代码。所以我需要你的帮助进一步优化相同的方法。

Answer 1

您可以将所有给定的单词插入到trie中，并且仅在当前字符串是trie中某个单词的前缀时继续沿路径搜索。

示例实现（基于您的代码，进行一些修改）：

struct TrieNode {
    TrieNode* children[26];
    bool wordEnd, found;
    ~TrieNode() {
        for (auto n : children) delete n;
    }
} *root;
void insert(const string& s) {
    auto curr = root;
    for (char c : s) {
        c -= 'a';
        if (!curr->children[c]) curr->children[c] = new TrieNode();
        curr = curr->children[c];
    }
    curr->wordEnd = true;
}
class Solution {
private:
    bool safe(int i, int j, vector<vector<bool>> &vis) {
        return i >= 0 && i < vis.size() && j >= 0 && j < vis[0].size() && !vis[i][j];
    }
    void solve(vector<string> &ans, vector<vector<char>>& board, vector<vector<bool>> &vis, string& s, TrieNode* node, int row, int col){
        if (!safe(row, col, vis) || !(node = node->children[board[row][col] - 'a'])) return;
        s += board[row][col];
        if (node->wordEnd && !node->found) node->found = true, ans.push_back(s);
        vis[row][col] = true;
        solve(ans, board, vis, s, node, row + 1, col); 
        solve(ans, board, vis, s, node, row - 1, col); 
        solve(ans, board, vis, s, node, row, col + 1); 
        solve(ans, board, vis, s, node, row, col - 1); 
        vis[row][col] = false;
        s.pop_back();
    }
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        root = new TrieNode();
        for (const auto& word : words) insert(word);
        vector<vector<bool>> vis(board.size(),vector<bool>(board[0].size(),0));
        string curr;
        vector<string> ans;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                solve(ans, board, vis, curr, root, i, j);
            }
        }
        delete root;
        return ans;
    }
};

请注意，有一个更快的 trie 实现，它不执行动态内存分配（而是使用问题约束），但对于此问题来说不是必需的，并且往往更难阅读。