478,回溯算法解单词搜索
Memory is a wonderful thing if you don't have to deal with the past.
如果你不必纠缠过去,那么回忆是一件非常美好的事情。
问题描述
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
提示:
board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3
回溯算法解决
这题是让判断给定的单词是否在二维网格中,所以最简单的一种方式就是使用dfs,沿着一个点往他的4个方向判断,如果最后能找到给定的单词就返回true,否则就返回false。
回溯算法实际上就是一个类似枚举的搜索尝试过程,也就是一个个去试,我们解这道题也是通过一个个去试,下面就用示例1来画个图看一下
他是从矩形中的一个点开始往他的上下左右四个方向查找,这个点可以是矩形中的任何一个点,所以代码的大致轮廓我们应该能写出来,就是遍历矩形所有的点,然后从这个点开始往他的4个方向走,因为是二维数组,所以有两个for循环,代码如下
1public boolean exist(char[][] board, String word) {
2 char[] words = word.toCharArray();
3
4 //下面两个for循环,来遍历数组的每一个值
5 for (int i = 0; i < board.length; i++) {
6 for (int j = 0; j < board[0].length; j++) {
7 //从[i,j]这个坐标开始查找,如果能查找到,直接
8 // 返回true,后面就不需要再查找了
9 if (dfs(board, words, i, j, 0))
10 return true;
11 }
12 }
13 return false;
14}
这里关键代码是dfs这个函数,因为每一个点都可以往他的4个方向查找,所以我们可以把它想象为一棵4叉树,就是每个节点有4个子节点,而树的遍历我们最容易想到的就是递归,我们来大概看一下
1boolean dfs(char[][] board, char[] word, int i, int j, int index) {
2 if (边界条件的判断) {
3 return;
4 }
5
6 一些逻辑处理
7
8 boolean res;
9 //往右
10 res = dfs(board, word, i + 1, j, index + 1)
11 //往左
12 res |= dfs(board, word, i - 1, j, index + 1)
13 //往下
14 res |= dfs(board, word, i, j + 1, index + 1)
15 //往上
16 res |= dfs(board, word, i, j - 1, index + 1)
17 //上面4个方向,只要有一个能查找到,就返回true;
18 return res;
19}
最终的完整代码如下
1public boolean exist(char[][] board, String word) {
2 char[] words = word.toCharArray();
3 for (int i = 0; i < board.length; i++) {
4 for (int j = 0; j < board[0].length; j++) {
5 //从[i,j]这个坐标开始查找
6 if (dfs(board, words, i, j, 0))
7 return true;
8 }
9 }
10 return false;
11}
12
13boolean dfs(char[][] board, char[] word, int i, int j, int index) {
14 //边界的判断,如果越界直接返回false。index表示的是查找到字符串word的第几个字符,
15 //如果这个字符不等于board[i][j],说明验证这个坐标路径是走不通的,直接返回false
16 if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[index])
17 return false;
18 //如果word的每个字符都查找完了,直接返回true
19 if (index == word.length - 1)
20 return true;
21 //把当前坐标的值保存下来,为了在最后复原
22 char tmp = board[i][j];
23 //然后修改当前坐标的值
24 board[i][j] = '.';
25 //走递归,沿着当前坐标的上下左右4个方向查找
26 boolean res = dfs(board, word, i + 1, j, index + 1)
27 || dfs(board, word, i - 1, j, index + 1)
28 || dfs(board, word, i, j + 1, index + 1)
29 || dfs(board, word, i, j - 1, index + 1);
30 //递归之后再把当前的坐标复原
31 board[i][j] = tmp;
32 return res;
33}
总结
要想弄懂这题,首先要搞懂回溯算法,要想弄懂回溯算法,就要先要搞懂递归。关于递归和回溯算法之前有过详细介绍,可以看下
长按上图,识别图中二维码之后即可关注。
如果觉得有用就点个"赞"吧