C++ 9ms beats 97.92%

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

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