TLE in Word Search backtracking

Question

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?

You have to pass by board by reference to existsUtil because you are changing its content : board[i][j] = temp;, if you pass it by value a copy of the board will be made and the changes are made on the copy. (https://www.learncpp.com/cpp-tutorial/passing-arguments-by-value) — Pepijn Kramer, Oct 10 '21 at 05:22
What does your favourite C++ book say about passing by reference vs passing by value? — Evg, Oct 10 '21 at 06:09
`vector>` can be quite slow due to poor spatial locality. Each `vector` contains a separate block of memory which may not be anywhere near the blocks contained by the to other `vector`s, reducing the effectiveness of cache. Consider using a matrix like [the one described in this answer](https://stackoverflow.com/a/2076668/4581301) — user4581301, Oct 10 '21 at 06:28

score 2 · Accepted Answer · answered Oct 10 '21 at 10:13

I guess, you can do one optimization on the code to start dfs only from position where (words[i][j] == word[0])
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.
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;
    }
}

TLE in Word Search backtracking

1 Answers1