【递归 &回溯】Leecode-79. 单词搜索

【题目】

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

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

示例 1：

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

示例 2：

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

示例 3：

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

【题解】

题解1：

• 思路

     列出可能的树形图，对于给出的列表逐个遍历调用dfs

• 复杂度

         时间复杂度：O(n2)，空间复杂度：O(n)

• 代码

class Solution:

    direct = [(0,1), (0,-1), (1,0), (-1,0)]

    def exist(self, board: List[List[str]], word: str) -> bool:
        def backtrack(i,j,mark,board,word):
            if len(word) == 0:
                return True
            
            for direct in self.direct:
                cur_i = i+direct[0]
                cur_j = j+direct[1]

                if cur_i>=0 and cur_i < len(board) and cur_j >= 0 and cur_j < len(board[0]) and board[cur_i][cur_j] == word[0]:
                    if mark[cur_i][cur_j] == 1:
                        continue
                    mark[cur_i][cur_j] = 1
                    if backtrack(cur_i, cur_j, mark, board, word[1:]) == True:
                        return True
                    else:
                        mark[cur_i][cur_j] = 0

            return False
        
        m = len(board)
        if m == 0:
            return False
        n = len(board[0])
        mark = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:
                    mark[i][j] = 1
                    if backtrack(i,j,mark,board, word[1:]) == True:
                        return True
                    else:
                        mark[i][j] = 0
        return False