79. 单词搜索

1. 题目

给定一个 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 更大的情况下可以更快解决问题？

2. 思路

  • 已知题目需要判断矩阵中是否存在单词组成，并且可以从任意单元格开始
  • 初始化DIRECTIONS二维数组常量作为方向集合（分别代表这上下左右四个方向），同时定义访问标记数组visit，并将字符串单词转换为字符数组
  • 遍历字符矩阵的每一个单元格，并以此作为开头进行回溯判断是否可以由此单元格组成单词，如果由此单元格开始可以组成单词，则直接返回结果true，否则继续遍历下一个单元格
  • 回溯方法中，入参分别是单词字符数组(word)、单词匹配下标(wordIndex)、字符矩阵行坐标(row)和字符矩阵列坐标(col)
  • 进入回溯时，首先判断当前正在匹配的是否已经是单词的最后一个字符，如果是，则直接返回board[row][col] == word[wordIndex]，代表最终一位字符的判断
  • 如果不是最后一个字符匹配，则判断字符是否与字符矩阵的字符相等，如果不相等，则直接返回false
  • 如果当前字符与字符矩阵的字符相等，则从四个方向进行下一轮回溯，四个方向需要判断对应字符矩阵单元格是否已被范围，并确定下标的合法性，同时需要在回溯前标记访问数组，在回溯后清除访问数组

3. 代码

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
53
54
55
class Solution {
    public static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    private char[][] board;
    private boolean[][] visit;
    private int totalRow;
    private int totalCol;

    public boolean exist(char[][] board, String word) {
        totalRow = board.length;
        totalCol = board[0].length;
        this.board = board;
        this.visit = new boolean[totalRow][totalCol];
        var arr = word.toCharArray();

        for (var row = 0; row < totalRow; ++row) {
            for (var col = 0; col < totalCol; ++col) {
                visit[row][col] = true;
                if (helper(arr, 0, row, col)) {
                    return true;
                }
                visit[row][col] = false;
            }
        }

        return false;
    }

    private boolean helper(char[] word, int wordIndex, int row, int col) {
        if (wordIndex + 1 == word.length) {
            return word[wordIndex] == board[row][col];
        }

        if (word[wordIndex] == board[row][col]) {
            for (var i = 0; i < DIRECTIONS.length; ++i) {
                var direction = DIRECTIONS[i];
                var nextRow = direction[0] + row;
                var nextCol = direction[1] + col;

                if (isValid(nextRow, nextCol)) {
                    visit[nextRow][nextCol] = true;
                    if (helper(word, wordIndex + 1, nextRow, nextCol)) {
                        return true;
                    }
                    visit[nextRow][nextCol] = false;
                }
            }
        }

        return false;
    }

    private boolean isValid(int row, int col) {
        return row >= 0 && row < totalRow && col >= 0 && col < totalCol && !visit[row][col];
    }
}

4. 复杂度

  • 时间复杂度：O(M * N * 3 ^ L)，其中M和N分别为字符矩阵的长和宽，而除了第一次可能会有4个方向可走以外，后续每一步都仅有3个方向可走，L为对应的单词长度，由于回溯涵盖了剪枝，所以时间复杂度的上限是O(M*N*3^L)
  • 空间复杂度：O(M * N)，开辟了一个访问数组，长度为M * N，同时递归最深为 M * N

执行结果