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
|
public class WordSearch {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0) {
return false;
}
int l = board.length;
int w = board[0].length;
boolean[][] isVisited = new boolean[l][w];
for (int i = 0; i < l; i++) {
for (int j = 0; j < w; j++) {
if (helper(board, word, i, j, 0, isVisited)) {
return true;
}
}
}
return false;
}
private boolean helper(char[][] board, String word, int l, int w, int crt, boolean[][] isVisited) {
if (crt == word.length()) {
return true;
}
if (l < 0 || w < 0 || l >= board.length || w >= board[0].length || isVisited[l][w]) {
return false;
}
if (board[l][w] != word.charAt(crt)) {
return false;
} else {
isVisited[l][w] = true;
boolean result = helper(board, word, l + 1, w, crt + 1, isVisited) ||
helper(board, word, l - 1, w, crt + 1, isVisited) ||
helper(board, word, l, w - 1, crt + 1, isVisited) ||
helper(board, word, l, w + 1, crt + 1, isVisited);
isVisited[l][w] = false;
return result;
}
}
}
|