1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
private String word;
private char[][] board;
public boolean exist(char[][] board, String word) {
boolean ans = false;
int m = board.length;
int n = board[0].length;
this.word = word;
this.board = board;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == word.charAt(0)) {
ans |= dfs(0, i, j, new char[word.length()]);
}
}
}
return ans;
}
private boolean dfs(int i ,int x, int y, char[] path) {
if (i == word.length()) {
return true;
}
int m = board.length;
int n = board[0].length;
if (x >= m || x < 0 || y >= n || y < 0 || board[x][y] == '0') {
return false;
}
char ch = board[x][y];
if (ch != word.charAt(i)) return false;
board[x][y] = '0';
path[i] = ch;
boolean ans = false;
ans |= dfs(i+1, x+1, y, path);
ans |= dfs(i+1, x-1, y, path);
ans |= dfs(i+1, x, y+1, path);
ans |= dfs(i+1, x, y-1, path);
board[x][y] = ch;
return ans;
}
}
|
