题解 | #牛群定位系统#

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

1. 深度优先搜索遍历整个矩阵。我们对每个位置进行 DFS，将得到的字符串与目标单词列表中的单词进行比较，用 visited 矩阵记录当前位置是否被访问过，以避免重复访问，如果存在则将其加入结果集中

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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param board char字符型二维数组
# @param words string字符串一维数组
# @return string字符串一维数组
#
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        result = []

        for word in words:
            if self.exist(board, word):
                result.append(word)

        return result

    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        visited = [[False] * cols for _ in range(rows)]

        for i in range(rows):
            for j in range(cols):
                if self.dfs(board, word, i, j, 0, visited):
                    return True

        return False

    def dfs(
        self,
        board: List[List[str]],
        word: str,
        row: int,
        col: int,
        index: int,
        visited: List[List[bool]],
    ) -> bool:
        if index == len(word):
            return True

        if (
            row < 0
            or row >= len(board)
            or col < 0
            or col >= len(board[0])
            or visited[row][col]
            or board[row][col] != word[index]
        ):
            return False

        visited[row][col] = True

        directions = [
            [0, 1],  # 右
            [0, -1],  # 左
            [1, 0],  # 下
            [-1, 0],  # 上
        ]

        for dx, dy in directions:
            new_row, new_col = row + dx, col + dy

            if self.dfs(board, word, new_row, new_col, index + 1, visited):
                return True

        visited[row][col] = False

        return False