79. 单词搜索-Medium.md

Description

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

 

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示：

• board 和 word 中只包含大写和小写英文字母。
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

Solution

• 本题同样可以套回溯法模板。只是外层多套了一层循环
  • 遍历，以board中每个元素为起点，DFS回溯看是否满足条件
  • 在DFS内部可套模板
• 时间复杂度：$O()$
• 空间复杂度：$O()$

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        self.direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        
        self.rows = len(board)
        if self.rows == 0:
            return False
        self.cols = len(board[0])

        self.isVisit = [[False for j in range(self.cols)] for i in range(self.rows)]

        for row in range(self.rows):
            for col in range(self.cols):
                if self.backtrack(row, col, 0, board, word):
                    return True

        return False

    def backtrack(self, row, col, index, board, word):
        if index == len(word) - 1:
            return board[row][col] == word[index]

        self.isVisit[row][col] = True
        if board[row][col] == word[index]:
            for next_step in self.direction:
                next_row, next_col = row+next_step[0], col+next_step[1]
                if next_row >= 0 and next_row < self.rows \
                    and next_col >= 0 and next_col < self.cols \
                    and not self.isVisit[next_row][next_col] \
                    and self.backtrack(next_row, next_col, index+1, board, word):
                        return True
        
        self.isVisit[row][col] = False

        return False