C++ 9ms beats 97.92%


  • 0
    M

    Hi, to make it faster there are mainly two tricks here:

    1. Modify the original input for backtracking instead of creating a new hashtable (normally not recommended but works here).
    2. Early return. Before diving deep into a dfs tree path, check if the next tree node matches the next char in word.

    The code is not that short but straight forward.

    bool exist(vector<vector<char>>& board, string word) {
            if(board.empty() || board[0].empty()){
                return false;
            }
            int row = board.size(), col = board[0].size();
            for(int i = 0; i < row; ++i){
                for(int j = 0; j < col; ++j){
                    if(board[i][j] == word[0]){
                        if(dfs(board, word, 0, i, j)){
                            return true;
                        }
                    }
                }
            }
            return false;
        }
        
    bool dfs(vector<vector<char>>& board, const string& word, int pos, int r, int c){
            if(pos == word.length() - 1){
                return true;
            }
            char cur = board[r][c];
            board[r][c] = '.';
            if(r + 1 < board.size() && board[r + 1][c] == word[pos + 1] && dfs(board, word, pos + 1, r + 1, c)){
                return true;
            }
            if(r >= 1 && board[r - 1][c] == word[pos + 1] && dfs(board, word, pos + 1, r - 1, c)){
                return true;
            }
            if(c + 1 < board[0].size() && board[r][c + 1] == word[pos + 1] && dfs(board, word, pos + 1, r, c + 1)){
                return true;
            }
            if(c >= 1 && board[r][c - 1] == word[pos + 1] && dfs(board, word, pos + 1, r, c - 1)){
                return true;
            }
            board[r][c] = cur;
            return false;
        }
    

Log in to reply
 

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