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