[LeetCode in Python] 79 (M) word search 单词搜索

题目

https://leetcode-cn.com/problems/word-search/

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

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

解题思路

• 二重遍历，一旦发现首字符，即开始DFS
• DFS中，上下左右判断下一个字符是否是word[i+1]
• 如果遇到下一个字符，就继续DFS，否则就回溯

代码

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # - sanity check
        n_row = len(board)
        if not n_row: return False
        n_col = len(board[0])
        if not n_col: return False

        def dfs(row, col, i, seen):
            if i == len(word)-1: return True
            
            for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                nr,nc = row+dr, col+dc
                if (0<=nr<n_row) and (0<=nc<n_col) and ((nr,nc) not in seen):
                    if (i < len(word)-1) and (board[nr][nc] == word[i+1]):
                        seen.add((nr,nc))
                        if not dfs(nr,nc,i+1,seen):
                            seen.remove((nr,nc))
                        else:
                            return True
            return False

        for row in range(n_row):
            for col in range(n_col):
                if board[row][col] == word[0]:
                    seen = set()
                    seen.add((row,col))
                    if dfs(row, col, 0, seen):
                        return True
        
        return False