LeetCode-79 单词搜索

题目描述

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

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

数据样例

示例 1：

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

示例 2：

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

示例 3：

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 \leq m, n \leq 6$
  • $1 \leq word.length \leq 15$
  • $board$ 和 $word$ 仅由大小写英文字母组成

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

深度优先搜索 DFS - $O(N ^ 2 * 3 ^ K)$

深度优先搜索 DFS

题目是要在一个字母网格中寻找某个字符串。只能上下左右四个方向寻找。

题目的数据范围很小，因此我们只需要从每个位置开始向周围 $4$ 个方向搜索寻找匹配的字符串即可。

  • 每次向周围搜索，判断下一个搜索到的字符是否和当前字符串中对应字符匹配

PS：关于 $4$ 个方向如何通过 方向数组 实现见下面题目讲解

方向数组相关讲解：LeetCode-200 岛屿数量

具体可以结合代码注释来理解搜索过程。

时间复杂度 - $O(N ^ 2 * 3 ^ K)$

  • 每次会向周围三个方向枚举
  • 从每个格子开始枚举

因此整体复杂度最多 $O(N ^ 2 * 3 ^ K)$，但是其实不可能这么多，因为很多情况下，字符都无法匹配。

代码

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
func exist(board [][]byte, word string) bool {
    // 获取 board 数组的长宽
    n, m = len(board), len(board[0])
    // 初始化方向数组
    dx, dy = []int{-1, 0, 0, 1}, []int{0, -1, 1, 0}
    // 依次枚举网格中的每个位置
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            // 如果找到和字符串第一个字符 word[0] 匹配的位置 (i, j)，则从当前位置进行搜索
            if board[i][j] == word[0] {
                // 初始化一个标记数组，用于标记 DFS 搜索过程中，已经搜索过的点
                st := make([][]bool, n)
                for k := range st { st[k] = make([]bool, m) }
                // 如果从当前位置找到了答案，则说明可以在网格中找到给定的字符串，返回 true
                if dfs(board, word, 0, i, j, st) { return true }
            }
        }
    }
    // 如果全部可能的位置都寻找了一遍，均没有找到，则返回 false
    return false
}

var n, m int
var dx, dy []int

// board：题目给定的网格。word：题目给定需要寻找的字符串
// u: 表示当前已经从 board 网格找到 word 字符串的前 u 个字符了
// x, y: 表示当前在 board 网格中的位置
// st: 标记数组
func dfs(board [][]byte, word string, u, x, y int, st [][]bool) bool {
    // 如果 u 到 word 的最后一个字符了，说明所有字符都找到了，说明在网格中找到字符串 word 了，返回 true
    if u == len(word) - 1 { return true }
    // 搜索过的点标记为 true，避免再次搜索
    st[x][y] = true
    // 利用枚举方向数组来实现枚举周围 4 个方向
    for i := 0; i < 4; i++ {
        // 利用方向数组计算下一个搜索的位置 (a, b)
        a, b := x + dx[i], y + dy[i]
        // 如果搜索的位置超过网格边界，则跳过
        if a < 0 || b < 0 || a >= n || b >= m { continue }
        // 如果搜索的位置已经被标记了（说明搜索过了），或者搜索的位置不和当前字符串对应位置 (word[u + 1]) 匹配，则跳过
        if st[a][b] || board[a][b] != word[u + 1] { continue }
        // 合法，则搜索 (a, b) 位置，如果我们从这个方向搜索，可以匹配，则返回 true
        if dfs(board, word, u + 1, a, b, st) { return true }
    }
    // 回溯：将标记过的点清除标记
    st[x][y] = false
    // 如果从当前位置开始向周围 4 个方向搜索，均找不到字符串 word，则返回 false
    return false
}
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
class Solution {
public:
    const int dx[4] = {-1, 0, 0, 1};
    const int dy[4] = {0, -1, 1, 0};
    int n, m;

    bool dfs(vector<vector<char>>& board, string word, int u, int x, int y, vector<vector<bool>>& st) {
        if (u == word.size() - 1) return true;
        st[x][y] = true;
        for (int i = 0; i < 4; ++i) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || b < 0 || a >= n || b >= m) continue;
            if (st[a][b] || board[a][b] != word[u + 1]) continue;
            if (dfs(board, word, u + 1, a, b, st)) return true;
        }
        st[x][y] = false;
        return false;
    }

    bool exist(vector<vector<char>>& board, string word) {
        n = board.size(), m = board[0].size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (board[i][j] == word[0]) {
                    vector<vector<bool>> st(n, vector<bool>(m));
                    if (dfs(board, word, 0, i, j, st)) return true;
                }
            }
        }
        return false;
    }
};