题目描述

[EN | CN]

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

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

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示:

  • board 和 word 中只包含大写和小写英文字母。
  • 1 <= board.length <= 200。
  • 1 <= board[i].length <= 200。
  • 1 <= word.length <= 10^3。

解法 1:回溯法

回溯法的思想类似 DFS 找迷宫出口,先猛地往一个方向钻,走到死路就返回上一个路口,一直重复,直到找到出口为止。这道题中就可以用类似的思路来解。从每个元素开始找,往 4 个方向钻,如果匹配字符串的下一个字符就继续,如果所有方向都匹配不了则返回上一层,继续匹配。

思路很简单,写起来要注意技巧。我刚开始是用 while 里面套 4 个 if 来判断 4 个方向,每个 if 内部都要更新此时的元素索引 i、j 和单词已经匹配的长度 curr,匹配失败的时候需要「恢复现场」,非常麻烦且容易出错,不如额外定义一个使用 helper 方法来做递归。具体做法如下:

  1. helper 接收当前坐标 i、j 和当前已经遍历到的位置索引 curr;
  2. 如果 i、j 的位置已经超出了矩阵范围或者当前位置已经遍历过了,则返回 False;
  3. 如果 curr 已经走到了字符串的尽头,则返回 True;
  4. 否则,设置当前位置已经被访问过,然后尝试往四个方向走一步,递归调用 helper,如果其中一个返回 True 就成功,如果都 False 就失败。

这里的走四个方向可以用一个 if 来实现,区别只在对 i、j 的改变,因此让 helper 方法接受新的 i、j 作为参数,就可以用一个 if 来囊括 4 个方向的走法了。

复杂度分析略。

实现与结果如下:

 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
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        h, w = len(board), len(board[0])
        visited = [[False for _ in range(w)] for _ in range(h)]

        def exist_helper(i, j, curr):
            if (i < 0 or i >= h or j < 0 or j >= w or
                visited[i][j] or
                board[i][j] != word[curr]):
                return False

            if curr == len(word) - 1:
                return True

            visited[i][j] = True
            if (exist_helper(i - 1, j, curr + 1) or
                exist_helper(i + 1, j, curr + 1) or
                exist_helper(i, j - 1, curr + 1) or
                exist_helper(i, j + 1, curr + 1)):
                return True

            visited[i][j] = False
            return False

        for i in range(h):
            for j in range(w):
                if exist_helper(i=i, j=j, curr=0):
                    return True

        return False
  • 执行用时:240 ms,在所有 Python3 提交中击败了 81.13% 的用户。
  • 内存消耗:15 MB,在所有 Python3 提交中击败了 5.41% 的用户。
▲