一、题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" 输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" 输出：false
提示：
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board和word仅由大小写英文字母组成
二、解题思路
- 遍历整个二维网格，对于每一个格子，都以它为起点进行深度优先搜索（DFS）。
- 在DFS中，检查当前字符是否匹配单词的当前字符。
- 如果匹配，标记当前位置已访问，并递归地访问它的四个邻居（上、下、左、右）。
- 如果在某个时刻，我们已经访问了单词的所有字符，并且它们都匹配，那么返回true。
- 如果在任何时刻字符不匹配或者已经没有更多的邻居可以访问，那么回溯，撤销最后一步的标记，并返回false。
- 如果所有起点都尝试过，仍未找到匹配的单词，那么返回false。
三、具体代码
class Solution {
private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四个方向：右、下、左、上
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n]; // 记录是否访问过
// 遍历整个网格
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(board, word, 0, i, j, visited)) {
return true; // 找到匹配，返回true
}
}
}
return false; // 没有找到匹配，返回false
}
private boolean dfs(char[][] board, String word, int index, int x, int y, boolean[][] visited) {
// 如果已经访问过word的所有字符，返回true
if (index == word.length()) {
return true;
}
// 检查当前坐标是否越界或者字符不匹配或者已经访问过
if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || visited[x][y] || board[x][y] != word.charAt(index)) {
return false;
}
// 标记当前位置已访问
visited[x][y] = true;
// 尝试访问四个方向的邻居
for (int[] direction : directions) {
int newX = x + direction[0];
int newY = y + direction[1];
if (dfs(board, word, index + 1, newX, newY, visited)) {
return true;
}
}
// 回溯，撤销访问标记
visited[x][y] = false;
return false;
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 对于每个单元格，我们可能需要进行深度优先搜索（DFS），最坏情况下，DFS会访问每个单元格一次。
- 单词的长度为
L，网格的大小为m x n。 - 在 DFS 中，我们最多会访问每个单元格四次（上、下、左、右）。
- 因此，时间复杂度为
O(m * n * 4^L)。这里的4^L是因为每次我们都有四个方向可以选择，并且我们可能需要探索单词的每个字符。
2. 空间复杂度
- 空间复杂度主要取决于递归调用栈的深度以及用于标记访问过的
visited数组。 - 递归调用栈的最大深度为
L，即单词的长度。 visited数组的大小为m x n。- 因此，空间复杂度为
O(m * n + L)。
（在这里，L 是单词的长度，m 和 n 分别是网格的行数和列数。）
五、总结知识点
-
回溯算法：这是一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化丢弃该解，即回溯并且再次尝试。
-
深度优先搜索（DFS）：这是一种用于遍历或搜索树或图的算法。沿着一个分支走到底，直到该路径上的最后一个节点被访问，然后回溯至上一个分叉点，继续遍历其他分支。
-
递归：这是一种编程技巧，函数自己调用自己。在DFS中经常使用递归，因为它非常适合用于探索分支。
-
二维数组：代码中的
board是一个二维字符数组，用于表示棋盘或网格。二维数组是数组的数组，可以用来表示矩阵或其他格状结构。 -
布尔数组：
visited是一个布尔类型的二维数组，用于跟踪在DFS过程中哪些位置已经被访问过，以避免重复访问同一个单元格。 -
边界检查：在访问网格的每个位置时，代码都会检查当前位置是否越界，即是否超出了数组的界限。
-
字符比较：代码中使用
board[x][y] != word.charAt(index)来检查当前网格中的字符是否与单词中的相应字符匹配。 -
循环和条件语句：代码中使用了
for循环来遍历网格的每个单元格，以及if语句来检查各种条件，如字符匹配、越界等。 -
数组初始化：在
exist方法中，directions数组和visited数组被初始化，以备后续使用。 -
方法重载：
exist和dfs是两个不同的方法，它们具有相同的名字exist，但是参数列表不同，这是方法重载的例子。 -
引用传递：在
dfs方法中，visited数组是通过引用传递的，这意味着在dfs中的任何修改都会影响到原始的visited数组。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
