# Why non-recursive got TLE but recursive accepted?

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

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

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