单词搜索

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

1
2
3
4
5
6
7
8
9
10
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

这道题目就是回溯算法,在回溯的时候要记录进来以防止下一次在循环到这个节点。再把边缘情况处理一下。

边缘情况包括word的数量大于board的节点数量,循环到边缘的情况,word和board的数量都为1.

我还增加了下次循环的方向以防止再次循环到来的地方。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
List<Integer> countList = new ArrayList<>();
public boolean exist(char[][] board, String word) {
char first = word.charAt(0);
if (board.length * board[0].length < word.length()) {
return false;
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] == first) {
countList.add(board[0].length * i + j);
if (word.length() == 1) {
return true;
}
if (a(board, word, 1, i - 1, j, 1, countList) ||
a(board, word, 1, i, j + 1, 2, countList) ||
a(board, word, 1, i + 1, j, 3, countList) ||
a(board, word, 1, i, j - 1, 4, countList)) {
return true;
}
countList.remove(board[0].length * i + j);
}
}
}
return false;
}
private boolean a(char[][] board, String word, int index, int i, int j, int k, List<Integer> countList) {
if (i < 0 || i == board.length
|| j < 0 || j == board[0].length
|| word.charAt(index) != board[i][j]
|| countList.contains(board[0].length * i + j)) {
return false;
}
if (index == word.length() - 1) {
return true;
}
countList.add(board[0].length * i + j);
switch (k) {
case 1: {
if (a(board, word, index + 1, i - 1, j, 1, countList) ||
a(board, word, index + 1, i, j + 1, 2, countList) ||
a(board, word, index + 1, i, j - 1, 4, countList)) {
return true;
} else {
countList.remove(countList.indexOf(board[0].length * i + j));
return false;
}
}
case 2: {
if (a(board, word, index + 1, i - 1, j, 1, countList) ||
a(board, word, index + 1, i, j + 1, 2, countList) ||
a(board, word, index + 1, i + 1, j, 3, countList)) {
return true;
} else {
countList.remove(countList.indexOf(board[0].length * i + j));
return false;
}
}
case 3: {
if (a(board, word, index + 1, i, j + 1, 2, countList) ||
a(board, word, index + 1, i + 1, j, 3, countList) ||
a(board, word, index + 1, i, j - 1, 4, countList)) {
return true;
} else {
countList.remove(countList.indexOf(board[0].length * i + j));
return false;
}
}
case 4: {
if (a(board, word, index + 1, i - 1, j, 1, countList) ||
a(board, word, index + 1, i + 1, j, 3, countList) ||
a(board, word, index + 1, i, j - 1, 4, countList)) {
return true;
} else {
countList.remove(countList.indexOf(board[0].length * i + j));
return false;
}
}
}
return false;
}

最佳答案和我的思路大体是一样的,但是他优化了我的list,他直接是将相对应的值进行 ^= 256,这样保证了回溯的值变成了一个不可能出现的值,在回溯之后再将他变回来。但是呢,list在调试的时候有很直观的感觉,这个是优化的方法所不能达到的,你能深切的感受到计算机是如何处理这段回溯的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) return false;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (word.charAt(0) == board[i][j]) {
if (dfs(board, word, 0, i, j)) return true;
}
}
}
return false;
}
public boolean dfs(char[][] board, String word, int k, int i, int j) {
if (k == word.length()) return true;
if (i < 0 || i == board.length || j < 0 || j == board[i].length) return false;
if (board[i][j] != word.charAt(k)) return false;
board[i][j] ^= 256;
if (dfs(board, word, k + 1, i - 1, j) ||
dfs(board, word, k + 1, i + 1, j) ||
dfs(board, word, k + 1, i, j - 1) ||
dfs(board, word, k + 1, i, j + 1) ) return true;
board[i][j] ^= 256;
return false;
}