image.png
class Solution {
private int row;
private int col;
private boolean[][] used;
private List result = new ArrayList<>();
boolean res;
public boolean exist(char[][] board, String word) {
row = board.length;
col = board[0].length;
used = new boolean[row][col];
char[] words = word.toCharArray();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if(dfs(board, words, 0, i, j)) return true;
}
}
return false;
}
private boolean dfs(char[][] board, char[] word, int pos,int i,int j) {
// || used[i][j]
if (i<0 || j <0 || i>=row || j>=col || board[i][j]!=word[pos] || used[i][j]) {
return false;
}
if (pos == word.length-1) {
return true;
}
//result.add(board[i][j]);
// board[i][j]='\0';
used[i][j]=true;
res = dfs(board,word,pos+1,i-1,j) || dfs(board,word,pos+1,i+1,j) ||
dfs(board,word,pos+1,i,j-1) || dfs(board,word,pos+1,i,j+1);
// result.remove(pos);
// board[i][j]=word[pos];
used[i][j]=false;
return res;
}
}
