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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| package algorithm;
public class WordSearch {
public static 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 < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] == word.charAt(0)) {
if (dfs(board, visited, word, 0, i, j, m, n)) {
return true;
}
}
}
}
return false;
}
private static boolean dfs(char[][] board, boolean[][] visited, String word, int index, int row, int col, int m, int n) {
if ((row < 0 || row >= m) || (col < 0 || col >= n) || visited[row][col]) {
return false;
}
if (word.charAt(index) == board[row][col] && word.length() == index + 1) {
return true;
}
if (word.charAt(index) == board[row][col]) {
visited[row][col] = true;
if (dfs(board, visited, word, index + 1, row + 1, col, m, n)) {
return true;
}
if (dfs(board, visited, word, index + 1, row - 1, col, m, n)) {
return true;
}
if (dfs(board, visited, word, index + 1, row, col + 1, m, n)) {
return true;
}
if (dfs(board, visited, word, index + 1, row, col - 1, m, n)) {
return true;
}
visited[row][col] = false;
}
return false;
}
public static void main(String[] args) {
char[][] board = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
String word = "ABCCED";
System.out.println(exist(board, word));
board = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
word = "SEE";
System.out.println(exist(board, word));
board = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
word = "ABCB";
System.out.println(exist(board, word));
}
}
|
