leetcode79:单词搜索
原题地址：79. 单词搜索 - 力扣（LeetCode）
题目描述
给定一个 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
解题思路
本问题可以使用回溯算法来实现，具体步骤如下：
- 遍历网格的每一个位置，从该位置开始尝试构建
word。 - 如果当前位置的字符与
word中当前的字符匹配，则尝试从当前位置出发继续匹配word的下一个字符。 - 使用 visited 数组标记当前位置，防止重复访问。
- 如果可以从当前位置匹配出完整的
word，返回true，否则回溯。 - 通过回溯算法遍历所有可能的路径，直到找到一个有效路径
源码实现
class Solution {
public boolean exist(char[][] board, String word) {
// 获取网格的行数和列数
int h = board.length, w = board[0].length;
// 记录访问过的网格位置，防止重复访问
boolean[][] visited = new boolean[h][w];
// 遍历整个网格，尝试从每个位置出发查找单词
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
// 如果从当前网格位置能够找到完整的单词，返回 true
boolean flag = check(board, visited, i, j, word, 0);
if (flag) {
return true;
}
}
}
// 如果遍历结束都没有找到单词，返回 false
return false;
}
// 使用回溯算法检查从 board[i][j] 开始是否能找到从 word[k] 开始的单词
public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
// 如果当前格子的字符不等于 word[k]，返回 false
if (board[i][j] != s.charAt(k)) {
return false;
}
// 如果已经匹配到 word 的最后一个字符，返回 true
else if (k == s.length() - 1) {
return true;
}
// 标记当前位置已访问
visited[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];
// 检查新位置是否在网格内
if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
// 如果新位置未被访问过，递归查找
if (!visited[newi][newj]) {
boolean flag = check(board, visited, newi, newj, s, k + 1);
if (flag) {
result = true;
break; // 如果找到有效路径，提前结束循环
}
}
}
}
// 回溯，标记当前位置为未访问
visited[i][j] = false;
return result; // 返回是否找到有效路径
}
}
复杂度分析
-
时间复杂度：
- 最坏情况下，回溯算法会遍历每一个可能的路径，对于每个单元格，都可能尝试四个方向进行递归查找，直到所有字符都被遍历。
- 假设网格的大小为
m x n，字符串的长度为L，那么在最坏情况下，算法的时间复杂度是：O(m * n * 4^L)。m * n：遍历所有的起始位置。4^L：对于每个位置，最多递归L层，每一层有四个方向可以选择。
-
空间复杂度：
- 回溯算法的递归深度最多为
L，因此栈的空间复杂度为O(L)。 - 另外，我们使用了一个大小为
m x n的visited数组，用来标记是否访问过某个位置。因此，空间复杂度为O(m * n)。
- 回溯算法的递归深度最多为