when I code the Leetcode problem [https://leetcode.com/problems/word-search/ 79 Word Search], I encounter the TLE problem:
my code for dfs is as following, which will result in TLE.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if(board.size() == 0 || board[0].size() == 0) return false;
int n = board.size();
int m = board[0].size();
vector<vector<bool>> passed(n, vector<bool>(m, false));
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(dfs(board, passed, word, i, j, 0)){
return true;
}
}
}
return false;
}
bool dfs(vector<vector<char>>& board, vector<vector<bool>>& passed,
string word, int x, int y, int pos){
int n = board.size();
int m = board[0].size();
vector<vector<int>> dirs = {{0,-1},{0,1},{1,0},{-1,0}};
if(pos == word.size())
return true;
if(x>=0 && x<n && y>=0 && y<m && !passed[x][y] && board[x][y] == word[pos]){
passed[x][y] = true;
for(auto dir: dirs){
int xx = x+dir[0];
int yy = y+dir[1];
// cout<<xx<<" "<<yy<<endl;
if(dfs(board, passed, word, xx, yy, pos+1))
return true;
}
passed[x][y] = false;
}
return false;
}
};

I tested another similar solution from [ this link], which will not cause TLE. Why?

Another Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
bool exist(vector<vector<char> > &board, string word) {
if (word.empty()) return true;
if (board.empty() || board[0].empty()) return false;
vector<vector<bool> > visited(board.size(), vector<bool>(board[0].size(), false));
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[i].size(); ++j) {
if (search(board, word, 0, i, j, visited)) return true;
}
}
return false;
}
bool search(vector<vector<char> > &board, string word, int idx, int i,
int j, vector<vector<bool> > &visited) {
if (idx == word.size()) return true;
if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() ||
visited[i][j] || board[i][j] != word[idx]) return false;
visited[i][j] = true;
bool res = search(board, word, idx + 1, i - 1, j, visited)
|| search(board, word, idx + 1, i + 1, j, visited)
|| search(board, word, idx + 1, i, j - 1, visited)
|| search(board, word, idx + 1, i, j + 1, visited);
visited[i][j] = false;
return res;
}
};