（LeetCodeHot100）79. 单词搜索——word-search

79. 单词搜索——word-search

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

img

1
2
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
输出：true

示例 2：

img

1
2
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"
输出：true

示例 3：

img

1
2
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"
输出：false

提示：

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

我的思绪错误答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Point {
    int x;
    int y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
class Solution {
    public boolean exist(char[][] board, String word) {
        int row = board.length;
        int col = board.length;
        int wordIndex = 0;
        Stack<Point> stack = new Stack<>();
        for (int boardIndex = 0; boardIndex < row * col; boardIndex++) {
            stack.add(new Point(boardIndex/col-1, (boardIndex-1)%col));
            while (!stack.isEmpty()) {
                if (board[stack.peek().x][stack.peek().y] != word.charAt(wordIndex)) {
                    continue;
                } else {
                    wordIndex++;
                    // 然后开始向上下左右试探，碰到壁了就返回
                    // 向右检查
                    if (stack.peek().y < col-1 && board[stack.peek().x][stack.peek().y+1] == word.charAt(wordIndex)) {
                        stack.add(new Point(stack.peek().x, stack.peek().y+1));
                        continue;
                    }
                    // 向下检查
                    if (stack.peek().x < row-1 && board[stack.peek().x+1][stack.peek().y] == word.charAt(wordIndex)) {
                        stack.add(new Point(stack.peek().x+1, stack.peek().y));
                        continue;
                    }
                    // 向左检查
                    if (stack.peek().y > 0 && board[stack.peek().x][stack.peek().y-1] == word.charAt(wordIndex)) {
                        stack.add(new Point(stack.peek().x, stack.peek().y-1));
                        continue;
                    }
                    // 向上检查
                    if (stack.peek().x > 0 && board[stack.peek().x-1][stack.peek().y] == word.charAt(wordIndex)) {
                        stack.add(new Point(stack.peek().x-1, stack.peek().y));
                        continue;
                    }
                }
            }
        }
        if (wordIndex == word.length()) {
            return true;
        } else {
            return false;
        }
    }
}

1. 矩阵列数计算错误（致命）

1
int col = board.length; // 错误：列数应该是 board[0].length
  • 矩阵的行数是 board.length，但列数应该是第一行的长度（board[0].length），除非矩阵是方阵，否则会导致列数计算错误，进而数组越界或坐标定位错误。

2. 起始坐标计算错误（致命）

1
stack.add(new Point(boardIndex/col-1, (boardIndex-1)%col));
  • 循环变量 boardIndex 从 0 到 row*col-1，但计算坐标时多减了 1，导致起始坐标从 (-1,-1) 开始，直接越界。
  • 正确计算：x = boardIndex / col，y = boardIndex % col（直接映射到矩阵的每个单元格）。

3. 未标记已访问的单元格（逻辑错误）

  • 回溯法的核心是避免重复访问同一单元格（比如走回头路），但你的代码没有标记已访问的位置，会导致无限循环或错误路径。

4. 栈的使用逻辑错误（逻辑错误）

  • 你只在栈中添加下一个匹配的单元格，但没有处理 “回溯”（即当前路径走不通时，弹出栈顶并回退 wordIndex）。
  • 例如：当上下左右都没有匹配的字符时，需要弹出当前单元格，wordIndex--，并取消该单元格的访问标记，重新尝试其他路径。

5. 循环中未重置状态（逻辑错误）

  • 每次尝试新的起始单元格时，没有重置 wordIndex、栈和访问标记，导致前一次的状态影响后续判断。

6. 匹配逻辑顺序错误（逻辑错误）

  • 先判断栈顶元素是否匹配当前 wordIndex，但栈顶元素是刚压入的，应该先标记访问，再判断匹配，然后尝试上下左右。

正确答案（顺着我的思路）147ms|击败62.72%

  • 用栈实现迭代式回溯（而非递归），需要在栈中存储坐标 + 当前单词索引 + 已访问状态，并手动处理回溯时的状态重置（弹出栈顶、wordIndex--、撤销访问标记），逻辑较复杂，递归实现更简洁高效。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    // 恢复正确的方法签名：接收 board 和 word 两个参数
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        int row = board.length;
        int col = board[0].length; // 修正：列数 = 第一行长度（非方阵也适用）
        boolean[][] visited = new boolean[row][col]; // 标记已访问单元格，避免重复

        // 遍历每个单元格作为起始点
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 起始字符匹配时，开始回溯查找
                if (backtrack(board, visited, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    // 回溯辅助函数：x,y=当前坐标，index=当前要匹配的单词索引
    private boolean backtrack(char[][] board, boolean[][] visited, int x, int y, String word, int index) {
        // 终止条件：所有字符都匹配成功
        if (index == word.length()) {
            return true;
        }
        // 边界/合法性检查：越界、已访问、字符不匹配，直接返回false
        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; // 标记当前单元格为已访问（选择当前路径）

        // 尝试上下左右四个方向（递归回溯）
        boolean up = backtrack(board, visited, x - 1, y, word, index + 1);
        boolean down = backtrack(board, visited, x + 1, y, word, index + 1);
        boolean left = backtrack(board, visited, x, y - 1, word, index + 1);
        boolean right = backtrack(board, visited, x, y + 1, word, index + 1);

        // 任意方向匹配成功，直接返回true
        if (up || down || left || right) {
            return true;
        }

        visited[x][y] = false; // 回溯：撤销访问标记（尝试其他路径）
        return false;
    }
}

1. 引入访问标记数组 visited

  • 每次访问单元格时标记为 true，回溯时撤销标记（false），避免重复访问。

2. 改用递归回溯（更直观）

  • 递归函数backtrack

    负责：

    1. 检查边界和匹配状态；
    2. 标记访问；
    3. 尝试四个方向；
    4. 回溯撤销标记。

3. 正确处理回溯逻辑

  • 当四个方向都无法匹配时，撤销当前单元格的访问标记，返回 false，让上一层递归尝试其他方向。

4. 优化起始遍历

  • 直接用双重循环遍历每个单元格作为起始点，逻辑更清晰，避免栈初始化错误。

官方解答:264ms|击败16.59%

方法一：回溯

思路与算法

设函数 check(i,j,k) 表示判断以网格的 (i,j) 位置出发，能否搜索到单词 word[k..]，其中 word[k..] 表示字符串 word 从第 k 个字符开始的后缀子串。如果能搜索到，则返回 true，反之返回 false。函数 check(i,j,k) 的执行步骤如下：

  • 如果 board[i][j]≠word[k]，当前字符不匹配，直接返回 false。
  • 如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回 true。
  • 否则，遍历当前位置的所有相邻位置。如果从某个相邻位置出发，能够搜索到子串 word[k+1..]，则返回 true，否则返回 false。

这样，我们对每一个位置 (i,j) 都调用函数 check(i,j,0) 进行检查：只要有一处返回 true，就说明网格中能够找到相应的单词，否则说明不能找到。

为了防止重复遍历相同的位置，需要额外维护一个与 board 等大的 visited 数组，用于标识每个位置是否被访问过。每次遍历相邻位置时，需要跳过已经被访问的位置。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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++) {
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        if (board[i][j] != s.charAt(k)) {
            return false;
        } 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;
    }
}

复杂度分析

  • 时间复杂度：一个非常宽松的上界为 O(MN*⋅$3^L$)，其中 *M,N 为网格的长度与宽度，L 为字符串 word 的长度。在每次调用函数 check 时，除了第一次可以进入 4 个分支以外，其余时间我们最多会进入 3 个分支（因为每个位置只能使用一次，所以走过来的分支没法走回去）。由于单词长为 L，故 check(i,j,0) 的时间复杂度为 O($3^L$)，而我们要执行 O(MN) 次检查。然而，由于剪枝的存在，我们在遇到不匹配或已访问的字符时会提前退出，终止递归流程。因此，实际的时间复杂度会远远小于 Θ(MN⋅$3^L$)。
  • 空间复杂度：O(MN)。我们额外开辟了 O(MN) 的 visited 数组，同时栈的深度最大为 O(min(L,MN))。