Help: Why does my answer exceed time limit, how can I improve it?


  • 0
    Z

    class Solution {

    private:
    int count;
    string word;
    int** visited;
    bool flag;
    
    public:
    bool exist(vector<vector<char> >& board, string word) {
        
        flag = false;
        
        count = 0;
        Solution::word = word;
        
        if (word.empty()) {
            return true;
        }
        
        if (board.empty()) {
            return true;
        }
        
        int m = board.size();
        int n = board[0].size();
        
        visited = new int*[m];
        for (int i = 0; i < m; i++) {
            visited[i] = new int[n];
            memset(visited[i], 0, n*sizeof(board[0][0]));
        }
        
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == word[count] && flag == false) {
                    DFS_visit(board, i, j);
                }
            }
        }    
        
        return flag;
    }
    
    void DFS_visit(vector<vector<char> >& board, int i, int j) {
        if (flag == true) {
            return;
        }
        
        visited[i][j] = 1;
        count++;
        
        if (count == word.size()) {
            cout << count << endl;
            flag = true;
            return;
        }
        
        if (i < board.size()-1 && board[i+1][j] == word[count] && visited[i+1][j] == 0) {
            DFS_visit(board, i+1, j);
        } 
        
        if (i > 0 && board[i-1][j] == word[count] && visited[i-1][j] == 0) {
            DFS_visit(board, i-1, j);
        } 
        
        if (j > 0 && board[i][j-1] == word[count] && visited[i][j-1] == 0) {
            DFS_visit(board, i, j-1);
        } 
        
        if (j < board[0].size()-1 && board[i][j+1] == word[count] && visited[i][j+1] == 0) {
            DFS_visit(board, i, j+1);
        }
        
        count--;
        visited[i][j] = 0;
    }
    

    };


Log in to reply
 

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