【回溯法】——单词搜索

79. 单词搜索

一、题目难度

中等

二、相关标签与相关企业

[相关标签]
[相关企业]

三、题目描述

给定一个 $m\times 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. $m==board.length$
2. $n=board[i].length$
3. $1\le m,n\le 6$
4. $1\le word.length\le 15$
5. $board$ 和 $word$ 仅由大小写英文字母组成

六、进阶

你可以使用搜索剪枝的技术来优化解决方案，使其在 $board$ 更大的情况下可以更快解决问题。

思路

• 本题：
  def exist(self, board: List[List[str]], word: str) -> bool:
• 传入网格board和目标单词word
• 定义dfs函数用来专门寻找，输入参数当前格子位置（i，j）以及要找的单词word里对应的位置k,dfs(i, j, k)
• return any(dfs(i, j, 0) for i in range(m) for j in range(n))对board每个位置(i, j)作为起点进行dfs，只要有一次找到了，true,结果就返回true！

dfs具体思路

1. 检查当前格子(i, j)的字符board[i][j]与目标单词的k位置的字符word[k]是否匹配。
   • 没匹配：
     • 注意后续会进行逐层递归调用，回溯
     • 即，后面会向着四个方向全部进行dfs搜索，
     • 全都看过了，递归回来了，整个过程中一次也没有找到目标单词，没有成功return True
     • 就可以对（i，j）这个位置返回Flase了
     • 宣告从这个位置开始找是找不到的
   • 否则说明匹配
   • 匹配成功相当于往前走了一步
   • 检查走到头了吗（完全匹配）
     • k走到len(word)-1 就表示到头了
     • 返回true
   • 除此之外，（i, j ）与k匹配成功但是k没到尽头！
     • 先标记当前位置(i, j)为已探索，后续dfs如果折返回到这里，会识别出已探索，或者因为无法匹配直接返回flase
   • 然后就是本题重点，对相邻的四个格子进行递归调用dfs，相当于往下个路口走
   • 遍历四个方向：for x, y in (上下左右), (。), (。), (。):
   • 不能碰壁：if 没碰壁（xy在board的范围内）：
   • 调用自身递归：更新k+1 ,dfs(x, y, k+1)
     • 注意这样写是错的！！
     • 这样只是去相邻格子找了，但是没管找的结果，（没按要求返回TRUE）
     • 比如： 可能会已经找到了单词，还继续傻乎乎去相邻格子找
     • 所以：if dfs(x, y, k+1): return true才是对的
     • 调用dfs后,用if判断其返回的值，如果返回true就说明找到了，这时候任务完成！
   • 递归后，说明当前节点的所有可能都已探索！
   • 将当前位置恢复,后面从其他起点(i，j)开始找！board[i][j] = word[k]
   • 如果以上不断递归都没有找到，则return false
   • 最后对所有起点用dfs！
   • return any(dfs(i,j,k) for i in xxx for j in xxxx)

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

        # 定义深度优先搜索函数dfs，从给定位置(i, j)尝试匹配目标单词对应字符
        def dfs(i: int, j: int, k: int) -> bool:
            """
            深度优先搜索函数：用于在二维字符网格的特定位置尝试匹配目标单词的字符

            :param i: 当前所在行索引 
            :param j: 当前所在列索引
            :param k: 已经匹配到的目标单词中的第几个字符，用于跟踪匹配进度
            :return : 在当前位置及后续搜索中能否成功匹配整个目标单词，返回tf
            """
            # 如果当前网格位置的字符与对应单词中对应位置的字符不能匹配，直接返回f
            if board[i][j] != word[k]:
                return False
            
            # 如果已经匹配到目标单词的最后一个字符
            if k == len(word) - 1: # 说明当前搜索路径下成功匹配了整个目标单词
                return True        # 返回true

            board[i][j] = ''     # 标记当前位置(i, j)已访问

            # 遍历当前位置的所有路径（相邻的四个格子）
            for x, y in (i, j - 1), (i, j + 1), (i + 1, j), (i - 1, j):
                # 但是要确保该路径可行（没撞墙）：
                if 0 <= x < m and 0 <= y < n:
                    # 递归调用dfs，继续在相邻格子中匹配目标单词的下一个字符
                    if dfs(x, y, k + 1):
                        # 如果在某个相邻各自以及后续搜索中能够匹配成功整个单词
                       return True
            #  将当前位置的字符恢复，因为之前只是为了标记临时修改了
            board[i][j] = word[k]

            # 如果对于当前位置的四个相邻格子递归搜索后仍未找到完整目标单词返回f
            return False

        return any(dfs(i, j, 0) for i in range(m) for j in range(n))