Why non-recursive got TLE but recursive accepted?


  • 0
    G

    Here is code.
    It is exactly same. And on my computer use time ./a.out, both them get 0.000s on largest example. I am confused about the OJ.

    Non-recusive one:

    class Solution {
    public:
        bool dfs(vector<vector<char> > &bd, vector<vector<bool> > &re, int x, int y, string &s) {
            stack<tuple<int, int, int, int> > sk;
            sk.push(make_tuple(x, y, 0, 0));
            bool sol = false;
            while (sk.size() > 0) {
                auto piece = sk.top();
                int i = get<0>(piece);
                int j = get<1>(piece);
                int loc = get<2>(piece);
                int state = get<3>(piece);
                sk.pop();
                if (loc == s.size()) sol = true;
                if (sol == true) break;
                if (i < 0 || i >= bd.size() || j < 0 || j >= bd[0].size()) continue;
                if (state == 0 && re[i][j] == true) continue;
                if (bd[i][j] != s[loc]) continue;
                if (state == 0) {
                    re[i][j] = true;
                    sk.push(make_tuple(i, j, loc, 1));
                    sk.push(make_tuple(i + 1, j, loc + 1, 0));
                } else if (state == 1) {
                    sk.push(make_tuple(i, j, loc, 2));
                    sk.push(make_tuple(i - 1, j, loc + 1, 0));
                } else if (state == 2) {
                    sk.push(make_tuple(i, j, loc, 3));
                    sk.push(make_tuple(i, j + 1, loc + 1, 0));
                } else if (state == 3) {
                    sk.push(make_tuple(i, j, loc, 4));
                    sk.push(make_tuple(i, j - 1, loc + 1, 0));
                } else if (state == 4) {
                    re[i][j] = false;
                }
                
            }
            return sol;
        }
        bool exist(vector<vector<char> > &board, string word) {
            if (board.size() == 0 || word.size() == 0) return false;
            bool sol = false;
            int M = board.size();
            int N = board[0].size();
            vector<vector<bool> > re(M, vector<bool>(N, false));
            for (int i = 0; i < M; ++i) {
                for (int j = 0; j < N; ++j) {
                    if (board[i][j] == word[0] && sol == false) {
                        sol = dfs(board, re, i, j, word);
                    } 
                }
            }
            return sol;
        }
    }; 
    

    Recursive one:

    class Solution {
    public:
        bool inline dfs(const vector<vector<char> > &bd, vector<vector<bool> > &re, int x, int y, int loc, const string &s) {
            if (loc == s.size()) return true;
            if (x < 0 || x >= bd.size() || y < 0 || y >= bd[0].size() || re[x][y] == true || bd[x][y] != s[loc]) return false;
            bool sol = false;
            re[x][y] = true;
            if (sol == false) sol = dfs(bd, re, x + 1, y, loc + 1, s);
            if (sol == false) sol = dfs(bd, re, x - 1, y, loc + 1, s);
            if (sol == false) sol = dfs(bd, re, x, y + 1, loc + 1, s);
            if (sol == false) sol = dfs(bd, re, x, y - 1, loc + 1, s);
            re[x][y] = false;
            return sol;
        }
        bool exist(vector<vector<char> > &board, string word) {
            if (board.size() == 0 || word.size() == 0) return false;
            bool sol = false;
            int M = board.size();
            int N = board[0].size();
            vector<vector<bool> > re(M, vector<bool>(N, false));
            for (int i = 0; i < M; ++i) {
                for (int j = 0; j < N; ++j) {
                    if (board[i][j] == word[0] && sol == false) {
                        sol = dfs(board, re, i, j, 0, word);
                    } 
                }
            }
            return sol;
        }
    };

  • 0
    T

    Which input got TLE? Understanding how it behaves on that input may help.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.