题解 | #童谣寻找问题#

• 题目考察的知识点 : 深度优先搜索，递归
• 题目解答方法的文字分析：

1. 通过深度优先搜索（DFS）遍历整个网格，查找是否存在目标单词。我们定义一个search函数，在函数中判断当前搜索的字符是否与目标字符相等，如果相等，则继续向四个方向搜索下一个字符。在搜索下一个字符之前，我们需要将当前格子标记为已经被使用过，以防止重复使用同一个格子。如果已经找到了目标单词的所有字符，则返回True；否则，如果四个方向都搜索完毕仍然没有找到，则回溯，将当前格子标记为未使用过，并返回False

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param board char字符型二维数组
# @param word string字符串
# @return bool布尔型
#
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        visited = [[False] * n for _ in range(m)]  # 定义一个二维数组表示每个格子是否已经被使用过

        # 定义一个函数用于在网格中搜索是否存在目标单词
        def search(i, j, k):
            # 如果当前搜索的字符与目标字符相等，则继续搜索下一个字符
            if board[i][j] == word[k]:
                # 如果已经找到了目标单词的所有字符，则返回True
                if k == len(word) - 1:
                    return True
                # 否则，继续向四个方向搜索下一个字符
                else:
                    visited[i][j] = True  # 标记当前格子已经被使用过
                    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                        nx, ny = i + dx, j + dy
                        # 如果下一个格子没有越界且没有被使用过，则继续搜索
                        if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                            if search(nx, ny, k + 1):
                                return True
                    visited[i][j] = False  # 回溯，将当前格子标记为未使用过

            return False

        # 在网格中搜索是否存在目标单词
        for i in range(m):
            for j in range(n):
                if search(i, j, 0):
                    return True

        return False