478，回溯算法解单词搜索

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

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}