2024/6/12 这两天天气只能用闷、潮、热来描述。整个人像被罩在为了饭菜保温的盖子里，喘气困难、粘稠的空气一次又一次打湿我。唯有空调救我，夏天来了。Anyway，昨天只做了一题，今天早点来做一题。
1、题目描述
2、逻辑分析
给定一个二维字符矩阵和一个单词，求单词是否在这个二维矩阵中，规则是，单词要按照顺序来，每次只能向上下、左右移动。大致就是这么个意思。我的想法是：既然需要单词必须按照字母排序，那么就以单词作为出发点，遍历单词，然后在矩阵中找是否有这个单词，找到后再与相连的单词进行位置计较，看是否符合规则。那么，怎么用代码来实现呢？我想不出来，故看了题解，题解使用回溯思想来解决。
整体思路：使用深度优先搜索（DFS）和回溯的思想实现。关于判断元素是否使用过，我用了一个二维数组 mark 对使用过的元素做标记。
- 首先遍历 board 的所有元素，先找到和 word 第一个字母相同的元素，然后进入递归流程。假设这个元素的坐标为 (i,
j)，进入递归流程前，先记得把该元素打上使用过的标记mark[i][j] = true。 - 好了，打完标记了，现在我们进入了递归流程。递归流程主要做了这么几件事： 从
(i, j)出发，朝它的上下左右试探，看看它周边的这四个元素是否能匹配 word 的下一个字母 - 如果匹配到了：带着该元素继续进入下一个递归
- 如果都匹配不到：返回 False
- 当 word 的所有字母都完成匹配后，整个流程返回 True
注意事项：
递归时元素的坐标是否超过边界
回溯标记mark[i][j] = 0以及 return 的时机
3、代码演示
public boolean exist(char[][] board, String word) {
// 获取board的行数和列数
int n = board.length, m = board[0].length;
// 创建一个与board同样大小的二维布尔数组，用于记录某个位置是否已被访问
boolean [][] mark = new boolean[n][m];
// 遍历board中的每一个字符
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
// 从当前字符开始，检查是否可以通过DFS找到整个word
boolean flag = check(board, mark, i, j, word, 0);
// 如果找到了，直接返回true
if(flag){
return true;
}
}
}
// 如果遍历完整个board都没有找到，返回false
return false;
}
// 递归检查函数
// 从(i,j)位置开始，检查board中是否包含字符串s的剩余部分（从索引k开始）
public boolean check(char[][] board, boolean[][] mark, int i, int j, String s, int k){
// 如果当前字符与s的第k个字符不匹配，返回false
if(board[i][j] != s.charAt(k)){
return false;
// 如果已经检查完s的所有字符，返回true
}else if(k == s.length() - 1){
return true;
}
// 标记当前位置为已访问
mark[i][j] = true;
// 定义四个方向的偏移量
int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
boolean result = false;
// 遍历四个方向
for(int[] dir : directions){
int newi = i + dir[0], newj = j + dir[1];
// 确保新位置在board范围内且未被访问过
if(newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length){
// 递归检查新位置
if(!mark[newi][newj]){
boolean flag = check(board, mark, newi, newj, s, k + 1);
// 如果在新位置找到了s的剩余部分，则result设为true并退出循环
if(flag){
result = true;
break;
}
}
}
}
// 回溯，将当前位置标记为未访问
mark[i][j] = false;
// 返回结果
return result;
}
是的，我基本上是照着题解敲出来的，敲的过程中印象加深，体会了dfs与回溯之间的关系与使用，以上注释较清晰，下面分析一下复杂度。
4、复杂度分析
- 时间复杂度：
O
(
M
N
⋅
3
L
)
\text{}O(MN\cdot3^{L})
O(MN⋅3L)。其中
M , N为网格的长度与宽度，L为单词 word 的长度。在每次调用函数check时，除了第一次可以进入 4 个分支以外，其余时间我们最多会进入 3 个分支（因为每个位置只能使用一次，所以走过来的分支没法走回去）。由于单词长为 L，故调用check的时间复杂度为 O ( 3 L ) O(3^{L}) O(3L)。要执行 O ( M N ) O(MN) O(MN)次检查。故时间复杂度为 O ( M N ⋅ 3 L ) \text{}O(MN\cdot3^{L}) O(MN⋅3L)。 - 空间复杂度：
O
(
M
N
)
O(MN)
O(MN)。因为需要创建一个与board一样大小的数组
mark来存储元素是否被访问过。
做完啦啦啦，拜拜啦!
标签：int,MN,mark,单词,boolean,HOT100,board,LeetCode,刷题 From： https://blog.csdn.net/weixin_48424783/article/details/139613942