友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

微信

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

LeetCode - 79. 单词搜索

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

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

示例 1：

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

示例 2：

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

示例 3：

0079 03 
输入：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 更大的情况下可以更快解决问题？

思路分析

典型的回溯题目，常规剪枝技巧如下：

0079 01

0079 02

除了常规剪枝技巧外，还有两个优化点：

  1. 先判断字母出现次数是否满足要求。网友戏称为可行性剪枝。

  2. 如果结尾字母出现次数更少，则将单词翻转，从尾部开始查找，这样可以更少回溯。网友戏称为顺序剪枝。

  • 一刷

  • 二刷

  • 三刷

 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

/**
 * Runtime: 4 ms, faster than 89.90% of Java online submissions for Word Search.
 *
 * Memory Usage: 38.4 MB, less than 97.96% of Java online submissions for Word Search.
 *
 * Copy from: https://leetcode.com/problems/word-search/discuss/27658/Accepted-very-short-Java-solution.-No-additional-space.[Accepted very short Java solution. No additional space. - LeetCode Discuss]
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-03 17:31
 */
public boolean exist(char[][] board, String word) {
    if (Objects.isNull(board) || board.length == 0) {
        return false;
    }
    if (Objects.isNull(word) || word.length() == 0) {
        return false;
    }
    char[] chars = word.toCharArray();
    for (int y = 0; y < board.length; y++) {
        for (int x = 0; x < board[y].length; x++) {
            if (exist(board, y, x, chars, 0)) {
                return true;
            }
        }
    }
    return false;
}

private boolean exist(char[][] board, int y, int x, char[] word, int i) {
    if (i == word.length) {
        return true;
    }
    if (y < 0 || x < 0 || y == board.length || x == board[y].length) {
        return false;
    }
    if (board[y][x] != word[i]) {
        return false;
    }
    board[y][x] = Character.MAX_VALUE;
    boolean existable = exist(board, y - 1, x, word, i + 1)
            || exist(board, y, x + 1, word, i + 1)
            || exist(board, y + 1, x, word, i + 1)
            || exist(board, y, x - 1, word, i + 1);
    board[y][x] = word[i];
    return existable;
}

 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

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-09-21 21:39:49
 */
public boolean exist(char[][] board, String word) {
  for (int r = 0; r < board.length; r++) {
    for (int c = 0; c < board[r].length; c++) {
      if (board[r][c] == word.charAt(0)) {
        if (backtrack(board, r, c, word, 0)) {
          return true;
        }
      }
    }
  }
  return false;
}

private boolean backtrack(char[][] board, int row, int column,
                          String word, int idx) {
  if (idx >= word.length()) {
    return true;
  }
  if (row < 0 || row >= board.length
    || column < 0 || column >= board[row].length
    || board[row][column] == ' '
    || board[row][column] != word.charAt(idx)) {
    return false;
  }
  board[row][column] = ' ';
  boolean result = backtrack(board, row - 1, column, word, idx + 1)
    || backtrack(board, row + 1, column, word, idx + 1)
    || backtrack(board, row, column - 1, word, idx + 1)
    || backtrack(board, row, column + 1, word, idx + 1);
  board[row][column] = word.charAt(idx);
  return result;
}

 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-11-15 08:52:34
 */
public boolean exist(char[][] board, String word) {
  // 优化一：检查字母出现次数
  char[] counter = new char[52];
  for (char[] chars : board) {
    for (char c : chars) {
      counter[getIndex(c)]++;
    }
  }
  char[] cnt = new char[52];
  for (char c : word.toCharArray()) {
    cnt[getIndex(c)]++;
  }
  for (int i = 0; i < cnt.length; i++) {
    if (cnt[i] > counter[i]) {
      return false;
    }
  }

  // 优化二：如果最后字符出现次数更小，则从它开始，回溯次数更少
  int ti = getIndex(word.charAt(word.length() - 1));
  int hi = getIndex(word.charAt(0));
  if (cnt[ti] < cnt[hi]) {
    word = new StringBuilder(word).reverse().toString();
  }

  // 回溯查找
  for (int c = 0; c < board.length; c++) {
    for (int r = 0; r < board[c].length; r++) {
      boolean found = backtrack(board, c, r, word, 0);
      if (found) {
        return true;
      }
    }
  }
  return false;
}

private int getIndex(char c) {
  int index = c - 'A';
  if (c >= 'a') {
    index = (c - 'a') + 26;
  }
  return index;
}

private boolean backtrack(char[][] board, int column, int row,
                          String word, int index) {
  if (index == word.length()) {
    return true;
  }
  if (column < 0 || board.length <= column
    || row < 0 || board[column].length <= row
    || board[column][row] != word.charAt(index)) {
    return false;
  }
  board[column][row] = '.';
  // 上
  boolean found = backtrack(board, column - 1, row, word, index + 1);
  if (found) {
    return true;
  }
  // 下
  found = backtrack(board, column + 1, row, word, index + 1);
  if (found) {
    return true;
  }
  // 左
  found = backtrack(board, column, row - 1, word, index + 1);
  if (found) {
    return true;
  }
  // 右
  found = backtrack(board, column, row + 1, word, index + 1);
  if (found) {
    return true;
  }
  board[column][row] = word.charAt(index);
  return false;
}

参考资料

  1. 79. 单词搜索 - 极致优化！代码击败接近 100%！

  2. 79. 单词搜索 - 回溯，清晰图解

  3. 79. 单词搜索 - 「手画图解」回溯思路的形成与细节

  4. 79. 单词搜索 - 官方题解

← Previous: 78. 子集 | ↑ Up: LeetCode 解题笔记 | Next: 80. 删除有序数组中的重复项 II →