TNotes.leetcode

Appearance

0079. 单词搜索【中等】

0079. 单词搜索【中等】 ​

1. 📝 题目描述 ​

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

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

示例 1：

img

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

示例 2：

img

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

示例 3：

img

txt
输入：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. 🎯 s.1 - 回溯 ​

c
int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

bool dfs(char** board, int m, int n, char* word, int k, int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k])
        return false;
    if (word[k + 1] == '\0')
        return true;

    char temp = board[i][j];
    board[i][j] = '\0'; // 标记已访问

    bool found = false;
    for (int d = 0; d < 4; d++) {
        if (dfs(board, m, n, word, k + 1, i + dirs[d][0], j + dirs[d][1])) {
            found = true;
            break;
        }
    }

    board[i][j] = temp; // 回溯恢复
    return found;
}

bool exist(char** board, int boardSize, int* boardColSize, char* word) {
    int m = boardSize, n = boardColSize[0];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (dfs(board, m, n, word, 0, i, j))
                return true;
    return false;
}
js
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  const m = board.length,
    n = board[0].length

  const dfs = (i, j, k) => {
    if (k === word.length) return true
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== word[k])
      return false

    const temp = board[i][j]
    board[i][j] = '\0' // 标记已访问

    const found =
      dfs(i + 1, j, k + 1) ||
      dfs(i - 1, j, k + 1) ||
      dfs(i, j + 1, k + 1) ||
      dfs(i, j - 1, k + 1)

    board[i][j] = temp // 回溯恢复
    return found
  }

  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++) if (dfs(i, j, 0)) return true
  return false
}
py
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

        def dfs(i: int, j: int, k: int) -> bool:
            if k == len(word):
                return True
            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:
                return False

            temp = board[i][j]
            board[i][j] = "\0"  # 标记已访问

            found = (
                dfs(i + 1, j, k + 1)
                or dfs(i - 1, j, k + 1)
                or dfs(i, j + 1, k + 1)
                or dfs(i, j - 1, k + 1)
            )

            board[i][j] = temp  # 回溯恢复
            return found

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False
  • 时间复杂度：O(m×n×3L)，其中 L 是单词长度，每个位置最多向 3 个方向扩展（排除来路）
  • 空间复杂度：O(L)，递归栈深度最多为单词长度

算法思路：

  • 枚举网格中每个位置作为起点，从该位置开始 DFS 匹配单词
  • DFS 时，若当前字符匹配 word[k]，将其临时修改为 '\0' 标记已访问，向四个方向递归匹配下一个字符
  • 递归返回后恢复原字符（回溯），保证不影响其他路径的搜索
  • 若 k == word.length 说明所有字符已匹配成功，返回 true

Discussions