LeetCode-每日一题（单词检索）

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

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

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # 定义四个方向,y+1(下)，y-1(上)，x+1(右)，x-1(左)
        directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        # 行数
        rows = len(board)
        # 列数
        cols = len(board[0])
        # 边界条件
        if rows == 0:
            return False
        # 对检索路径进行标记
        visited = [[False for _ in range(cols)] for _ in range(rows)]

        def backtrace(i, j, index):
            if index == len(word) - 1:
                return board[i][j] == word[index]

            if board[i][j] == word[index]:
                visited[i][j] = True
            
                for direct in directs:
                    new_i = i + direct[0]
                    new_j = j + direct[1]
                    if 0 <= new_i < rows and 0 <= new_j < cols and visited[new_i][new_j] == False:
                        if backtrace(new_i, new_j, index + 1):
                            return True
                visited[i][j] = False
            return False

        # 按照行和列检索
        for i in range(rows):
            for j in range(cols):
                if backtrace(i, j, 0):
                    return True
        return False