单词搜索

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

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

 

示例:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/word-search

依题意,这道题的要求是:1、要按照字母顺序
2、不能重复利用字母

所以我们要去判断该单词是否在该二维数组中,我们要先找到它的首字母,然后在从首字母向四周扩散搜索:
具体操作:

      • 默认从初始原点(0,0)开始搜索
      • 若不匹配则返回False
      • 若单词索引结束则返回True
      • 每次访问都进行标记 令 visit[x][y] = True
      • 向四周访问,满足所有条件则返回True
      • 未找到则将该点返回visit[x][y] = False
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])
        row = [-1, 0, 1, 0]
        col = [0, -1, 0, 1]

        visit = [[False] * n for _ in range(m)]

        def dfs(x, y, idx):
            if board[x][y] != word[idx]:
                return False

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

            visit[x][y] = True

            for i in range(4):
                xd = x + row[i]
                yd = y + col[i]
                if 0 <= xd < m and 0 <= yd < n and not visit[xd][yd] and dfs(xd, yd, idx + 1):
                    return True
            visit[x][y] = False
            return False

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

 

点赞

发表评论

Title - Artist
0:00