图的遍历，回溯
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
思路：
网格搜索类型的题目需要马上联想到图的遍历问题，解法无非2种，DFS或者BFS。细节上的处理就是如何剪枝以减小复杂度。大部分时候，DFS的代码会简洁易懂一些（不需要借助队列），我们考虑用DFS实现。
我们用一个辅助函数 search 来进行DFS递归遍历。在函数中，我们用一个 StringBuilder sb 变量存储当前累计获取到的合法字符串。以当前末尾字符为出发点，向四周 可能的位置 探测。（「可能」指的是，下标不越界，并且此轮字符串遍历未访问过的网格。因此，我们还需要为本次遍历存储一个 visited 二维数组，记录是否访问过此网格。）
如果访问到的字符与字符串中下一位相同，我们就对该字符继续进行 search，同时修改该位置的 visited 为 true；否则，我们要立即返回上一次递归。为了让程序知道这次递归是否找到了目标字符串，我们给 search 一个 boolean 返回值。
对网格中的每个小格，我们都要以之为起点，用一个新的 sb 和 visited 数组进行遍历。每次都建立新的二维数组 visited 的话，不仅降低效率，而且每次都要申请额外 n² 的空间。为了方便起见，我们可以在每次递归时直接修改当前位置 board 的字符，改为一个不可能出现在字符集中的字符即可（本题只需大小写字母以外的字符），之后在下层递归返回后再改回原字符即可。
时间复杂度：O(n²)
空间复杂度：O(n)
实现：
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
| class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
StringBuilder sb = new StringBuilder(word);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (search(board, i, j, sb)) {
return true;
}
}
}
return false;
}
private boolean search(char[][] board, int i, int j, StringBuilder sb) {
char c = board[i][j];
if (c != sb.charAt(0)) {
return false;
}
sb.deleteCharAt(0);
board[i][j] = '\0';
if (sb.length() == 0) {
board[i][j] = c;
return true;
}
int m = board.length;
int n = board[0].length;
char next = sb.charAt(0);
if (i > 0 && board[i - 1][j] == next) {
if (search(board, i - 1, j, sb)) {
return true;
}
}
if (j > 0 && board[i][j - 1] == next) {
if (search(board, i, j - 1, sb)) {
return true;
}
}
if (i < m - 1 && board[i + 1][j] == next) {
if (search(board, i + 1, j, sb)) {
return true;
}
}
if (j < n - 1 && board[i][j + 1] == next) {
if (search(board, i, j + 1, sb)) {
return true;
}
}
sb.insert(0, c);
board[i][j] = c;
return false;
}
}
|
