Medium
看的答案，这种简单粗暴的DFS还是不会写. 抄过来又觉得很简单，多写几道多体会体会吧
class Solution {
//DFS
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (board[i][j] == word.charAt(0) && dfsHelper(board, word, i, j, 0, visited)){
return true;
}
}
}
return false;
}
private boolean dfsHelper(char[][] board, String word, int i, int j, int index, boolean[][] visited){
if (index == word.length()){
return true;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(index)){
return false;
}
visited[i][j] = true;
if (dfsHelper(board, word, i + 1, j, index + 1, visited) || dfsHelper(board, word, i - 1, j, index + 1, visited) ||
dfsHelper(board, word, i, j + 1, index + 1, visited) || dfsHelper(board, word, i, j - 1, index + 1, visited)){
return true;
}
visited[i][j] = false;
return false;
}
}
