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

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?

CodePudding user response：

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