Here is a problem from Leetcode: Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

I did simple backtracking with dfs, here is my code:

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;
    }
};

This code is giving TLE for larger inputs. But in the dfs function, if I pass the board parameter by referece, that is, if I pass vector<vector<char>> &board, it passes all test cases. Why is this happening?

CodePudding user response：

1. I guess, you can do one optimization on the code to start dfs only from position where (words[i][j] == word[0])

2. Secondly answering your question when you pass by value every time a new copy of 2d array is created in recursive calls which gives the TLE.

3. See My faster than 100% JAVA code, Hope this helps!

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;
    }
}