05 August 2008
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
1
2
3
4
5
6
7
8
9
10
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
这道题是比较明显的深搜
递归，回溯和DFS的区别
递归是一种算法结构，回溯是一种算法思想
一个递归就是在函数中调用函数本身来解决问题 回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”，意思就是对已经知道错误的结果没必要再枚举接下来的答案了，比如一个有序数列1,2,3,4,5，我要找和为5的所有集合，从前往后搜索我选了1，然后2，然后选3 的时候发现和已经大于预期，那么4,5肯定也不行，这就是一种对搜索过程的优化。
深度优先搜索（DFS）对于某一种数据结构来说，一般是树（搜索树是起记录路径和状态判断的作用），对于回溯和DFS，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。
为了减少存储空间，在深度优先搜索中，用标志的方法记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别了。
如同上面的比较，DFS有两种经典的做法，一是用跟原本二维数组同等大小的数组来记录是否visited过，其中元素为boolean， 如果二维数组board的当前字符和目标字符串word对应的字符相等，则对其上下左右四个邻字符分别调用DFS的递归函数，只要有一个返回true，那么就表示可以找到对应的字符串，否则就不能找到；第二是对第一种做法空间上的优化，每次用一个char来记录当前二维数组里面的char，在递归调用前用一个特殊的字符，比如‘#’，来代替当前字符说明已经检查过了，然后再递归调用后再改回来方便下次检查。
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
class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0) {
return false;
}
int rows = board.length;
int cols = board[0].length;
boolean[][] visited = new boolean[rows][cols];
// optional
// for (int i = 0; i < rows; i++) {
// Arrays.fill(visited[i], false);
// }
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (dfs(board, i, j, word, 0, visited)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, int i, int j, String word, int index, boolean[][] visited) {
if (index == word.length()) { //找完了
return true;
}
//已被访问过
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index) || visited[i][j]) {
return false;
}
visited[i][j] = true; //设定当前字符已被访问过
boolean isValid =
dfs(board, i - 1, j, word, index + 1, visited) ||
dfs(board, i + 1, j, word, index + 1, visited) ||
dfs(board, i, j - 1, word, index + 1, visited) ||
dfs(board, i, j + 1, word, index + 1, visited);
visited[i][j] = false; //回溯
return isValid;
}
}
优化空间，不用额外visited数组，修改当前值
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
class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0) {
return false;
}
int m = board.length, n = board[0].length;
int index = 0;//字符串的索引
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(board, word, index, i, j)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int index, int i, int j) {
if (index == word.length()) {//找完了
return true;
}
int m = board.length, n = board[0].length;
if (i < 0 || j < 0 || i >= m || j >= n
|| board[i][j] != word.charAt(index)) {//两个字符不相等
return false;
}
char temp = board[i][j];//临时存一下当前的字符,在当前DFS递归树的路径上
board[i][j] = '#';
boolean result = (dfs(board, word, index + 1, i - 1, j)//左
|| dfs(board, word, index + 1, i + 1, j)//右
|| dfs(board, word, index + 1, i, j - 1)//上
|| dfs(board, word, index + 1, i, j + 1));//下
board[i][j] = temp;//这步不要忘记，让“当前的”位置归为初始值，为别的路径的查找准备
return result;
}
}