单词搜索- python-dfs剪枝

题目：

思路：

参考：https://leetcode.cn/problems/word-search/solutions/2361646/79-dan-ci-sou-suo-hui-su-qing-xi-tu-jie-5yui2/?envType=study-plan-v2&envId=top-100-liked

深度优先搜索（DFS）+ 剪枝

• 深度优先搜索：即暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
• 剪枝：在搜索中，遇到“这条路不可能和目标字符串匹配成功”的情况，例如当前矩阵元素和目标字符不匹配、或此元素已被访问，则应立即返回，从而避免不必要的搜索分支。

代码：

class Solution: def exist(self, board: List[List[str]], word: str) -> bool: def dfs(i,j,k): if not 0<=i<len(board) or not 0<=j<len(board[0]) or board[i][j] != word[k]: return False if k == len(word)-1: return True board[i][j] = '' res = dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or dfs(i,j+1,k+1) or dfs(i,j-1,k+1) board[i][j] = word[k] return res for i in range(len(board)): for j in range(len(board[0])): if dfs(i,j,0):return True return False

算法解析：

• 递归参数：当前元素在矩阵board中的行列索引i和j，当前目标字符在word中的索引k。

• 终止条件：

  • false：​​​​​​​​​​​​​​(1) 行或列索引越界或(2) 当前矩阵元素与目标字符不同或(3) 当前矩阵元素已访问过 （ (3) 可合并至 (2) ）

  • true:k = len(word) - 1，即字符串word已全部匹配。

• 递推工作：​​​​​​​

  • 标记当前矩阵元素： 将board[i][j]修改为空字符''，代表此元素已访问过，防止之后搜索时重复访问。

  • 搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。

  • 还原当前矩阵元素： 将board[i][j]元素还原至初始值，即word[k]。
• 返回值：返回布尔量res，代表是否搜索到目标字符串。