c++algorithmdynamic-programmingrecursive-backtrackingloop-unrolling

Why is my code giving time-limit exceeded while a near identical code works just fine in LeetCode?


Ref: https://leetcode.com/problems/word-search/submissions/

Brief problem statement: Given a matrix of characters and a string, does the string exist in this matrix. Please refer the above link for details.

Solution-1 Gives time-limit exceeded.

class Solution {
public:
    int n;
    int m;
    bool search(vector<vector<char>>& board, const char* w, int i, int j){
        
        if(i < 0 || i >= m || j < 0 || j >= n || *w != board[i][j] || board[i][j] == '\0') return false;
        if(*(w+1) == '\0') return true;

        char t = board[i][j];
        board[i][j] = '\0';
        vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for(auto d: dir){
            bool temp = search(board, w+1, i + d[0], j + d[1]);
            if(temp) return true;
        }
        board[i][j] = t;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(search(board, word.c_str(), i, j)) return true;
            }
        }
        return false;
    }
};

Solution-2 Works fine. In fact faster than ~93 % of C++ submissions

class Solution {
public:
    int n;
    int m;
    bool search(vector<vector<char>>& board, const char* w, int i, int j){
        
        if(i < 0 || i >= m || j < 0 || j >= n || *w != board[i][j] || board[i][j] == '\0') return false;
        if(*(w+1) == '\0') return true;

        char t = board[i][j];
        board[i][j] = '\0';
        if(search(board, w+1, i -1, j) || search(board, w+1, i+1, j) || search(board, w+1, i, j-1) || search(board, w+1, i, j+1)) return true;
        board[i][j] = t;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(search(board, word.c_str(), i, j)) return true;
            }
        }
        return false;
    }
};

The only difference between these two solutions is the way I call the search function recursively within the search function.

In the solution-1 it is:

vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for(auto d: dir){
    bool temp = search(board, w+1, i + d[0], j + d[1]);
    if(temp) return true;
}

In solution-2 it is:

if(search(board, w+1, i -1, j) || search(board, w+1, i+1, j) || search(board, w+1, i, j-1) || search(board, w+1, i, j+1)) return true;

I think the second solution is like loop unrolling and while this partly explains why the second one is faster than the first one. Isn't it faster by only a constant factor. I mean asymptotically they are similar. I am just surprised that loop unrolling is causing my solution to go from TLE to faster than 93% solutions.

Basically, my question is, Is loop unrolling the only reason why the second solution is so fast, or am I missing something?


Solution

  • I am not sure about the time complexity of auto type! But if you remove the 2D vector construction from the recursive function, and instead of auto use the normal index-based loop to access the vector then you would pass the timelimit.

    class Solution {
    public:
        int n;
        int m;
        vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        bool search(vector<vector<char>>& board, const char* w, int i, int j){
            
            if(i < 0 || i >= m || j < 0 || j >= n || *w != board[i][j] || board[i][j] == '\0') return false;
            if(*(w+1) == '\0') return true;
    
            char t = board[i][j];
            board[i][j] = '\0';
            
            for(int r=0; r<4; r++){
                bool temp = search(board, w+1, i + dir[r][0], j + dir[r][1]);
                if(temp) return true;
            }
            board[i][j] = t;
            return false;
        }
        bool exist(vector<vector<char>>& board, string word) {
            m = board.size();
            n = board[0].size();
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(search(board, word.c_str(), i, j)) return true;
                }
            }
            return false;
        }
    };