[leetcode]70_单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
同一个单元格内的字母不允许被重复使用。示例 1：
A B C E
S F C S
A D E E
输入：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提示：
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

解题思路：【DFS + 回溯】

visited[i][j] == 1，表示此单元格已经被使用
字符串首字母位置集合positions = [(x1, y1),(x2, y2),……]
根据首字母位置DFS深度优先遍历：directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]，相邻单元格【上，下、左、右】递归：搜索某个方向的单元格回溯：若该单元格四个方向找不到，则将对应visited[i][j] = 0并回溯至上一个节点，搜索另外方向，剪枝：某方向单元格字符！=目标字符 or visited[i][j] == 1，直接切换为另一个方向（仅遍历条件情况：方向单元格字符==目标字符 or visited[i][j] ！= 1）终止条件：某一首字母位置出发递归找到所有字符，结果为True；全部首字母出发均未找到所有字符，结果为False

此解法题目类似：【华为OD】2024D卷——围棋的气_围棋的气 华为od-CSDN博客

class Solution:# 检查坐标（x,y）是否在棋盘范围内，防止DFS检查坐标越界def in_bounds(self, x, y, row, column):return 0 <= x < row and 0 <= y < columndef dfs(self, board, row, column, x, y, word, index, visited, res):#   DFS遍历完所有单词，均在单元格中找到时，修改结果res = True；其他保持默认res = Falseif index == len(word):res[0] = Truereturndirections = [(-1, 0), (1, 0), (0, -1), (0, 1)]#   遍历单元格的四个方位for d_x, d_y in directions:n_x, n_y = d_x + x, d_y + yif self.in_bounds(n_x, n_y, row, column):if board[n_x][n_y] == word[index] and not visited[n_x][n_y]:visited [n_x][n_y] = 1self.dfs(board,row, column, n_x, n_y, word, index + 1, visited, res)#   找不到，回溯visited [n_x][n_y] = 0#   单元格已经访问过 或者 单词不匹配；不做处理，保持默认res = False结果#   越界情况不统计def deal_with(self, board, word):#   行row = len(board)#   列column = len(board[0])#   访问数组visited = [[0] * column for _ in range(row)]#   首字母位置first_word_pos = []for i in range(row):for j in range(column):if board[i][j] == word[0]:first_word_pos.append((i, j))#   首字母不在board中，直接返回Falseif not first_word_pos :return False#   对每个首字母位置进行DFS，DFS内从word[1:]开始res = [False]#   使用列表数据类型，函数传入列表作为参数，再在DFS中改变res的值——类似全局变量效果for x, y in first_word_pos:visited[x][y] = 1self.dfs(board, row, column, x, y, word, 1, visited, res)#   存在从某个首字母位置，可以找到完整字符串，则直接返回Trueif res[0] == True:return Truevisited[x][y] = 0#   所有首字母位置均找不到，则返回Falsereturn False
if __name__ == '__main__':try:#   初始化网格board = eval(input())word = input().strip()solution = Solution()result = solution.deal_with(board, word)print(result)except Exception as e:print(e)

仅作为代码记录，方便自学自查自纠