词搜索回溯中的 TLE

Question

这是一道来自 Leetcode 的题目：给定一个 m x n 的字符板网格和一个字符串单词，如果网格中存在单词，则 return 为真。该词可以由顺序相邻单元格的字母构成，其中相邻单元格是水平或垂直相邻的。同一字母单元格不能使用多次。

我用 dfs 做了简单的回溯，这是我的代码：

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int index = 0;
        for(int i = 0; i < board.size(); i++) {
            for(int j = 0; j < board[0].size(); j++) {
                if(existsUtil(board, index, word, i, j))
                    return true;
            }
        }
    
        return false;
    }
    bool existsUtil(vector<vector<char>> board, int index, string word, int i, int j) {
        if(index >= word.length())
            return true;
        if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[index] || board[i][j] == '0')
            return false;

        char temp = board[i][j];
        board[i][j] = '0';
        index += 1;
        bool value = existsUtil(board, index, word, i + 1, j) || existsUtil(board, index, word, i, j - 1) || existsUtil(board, index, word, i - 1, j) || existsUtil(board, index, word, i, j + 1);
        board[i][j] = temp;
    
        return value;
    }
};

此代码为更大的输入提供 TLE。但是在dfs函数中，如果我通过referece传递了board参数，也就是我传递了vector<vector<char>> &board，它就通过了所有的测试用例。为什么会这样？

Answer 1

我猜，你可以对代码做一个优化，只从 (words[i][j] == word[0])
的位置开始 dfs
每次在递归调用中创建二维数组的新副本时传递值时再次回答您的问题，这给出了 TLE。
查看我的速度超过 100% JAVA 的代码，希望对您有所帮助！

class Solution {
    boolean flag = false;
    public boolean exist(char[][] board, String word) {

        for(int i = 0;i < board.length;i++){
            for(int j = 0;j < board[0].length;j++){
                if(board[i][j] == word.charAt(0)){
                    backtrack(board,word,1,i,j);
                    if(flag) return true;
                }
            }
        }

        return false;
    }

    void backtrack(char[][] board, String word, int p, int row, int col){
        if(board[row][col] > 255)
            return;
        else if(p > word.length() - 1){
            //System.out.println(asf);
            flag  = true;
            return;
        }

        board[row][col] ^= 256;
        //up
        if(row > 0 && board[row-1][col] == word.charAt(p)) {
            backtrack(board, word, p + 1, row - 1, col);
        }
        //down
        if(row < board.length - 1 && board[row+1][col] == word.charAt(p))
            backtrack(board,word, p+1,row+1,col);
        //left
        if(col > 0 && board[row][col-1] == word.charAt(p))
            backtrack(board,word, p+1,row,col-1);
        //right
        if(col < board[0].length - 1 && board[row][col+1] == word.charAt(p))
            backtrack(board,word, p+1,row,col+1);

        board[row][col] ^= 256;

        return;
    }
}

词搜索回溯中的 TLE

TLE in Word Search backtracking

c++

algorithm

pass-by-reference

depth-first-search

recursive-backtracking