题解 | #单词搜索#

有回溯版DFS

初始

题目要求相同位置不能重复访问，因此设置和输入矩阵一样形状的st[]，存矩阵中的位置是否被访问过：访问过置1，反之为0。

找到合法(不超过矩阵边界) 且 没有被访问过 且 和word首字符能匹配上 的位置为起点(x, y)：

1. 标记（x, y) 被访问st[x][y] = 1
2. 待匹配的字符串word = word[1:]

递归

终止条件：word完全匹配成功 len(word) == 0

递归过程：

以起点为中心，遍历上下左右四个方向

# 当前位置是x,y
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
for i in range(4):
  new_x = x + dx[i]
  new_y = y + dy[i]
  # ...对新位置new_x, new_y的操作

找到合法(不超过矩阵边界) 且 没有被访问过 且 和当前word首字符能匹配上 的位置为新的起点(new_x, new_y)：

1. 标记（new_x, new_y) 被访问st[new_x][new_y] = 1
2. 待匹配的字符串word = word[1:]

递归处理后续字符。

!!! 回溯：

假设当前位置是(x, y)，若dfs(x, y)都不满足条件，则释放(x, y)位置，st[x][y] = 0 且 word复原，首字母重新待匹配。判断下一个位置。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param board string字符串一维数组 
# @param word string字符串 
# @return bool布尔型
#
class Solution:
    def dfs(self, x, y, word):
        if len(word) == 0:
            return True
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        for i in range(4):
            new_x = x + dx[i]
            new_y = y + dy[i]
            if new_x < 0 or new_x >= self.m or new_y < 0 or new_y >= self.n: # 边界情况
                continue
            elif self.st[new_x][new_y] == 0 and self.board[new_x][new_y] == word[0]: # 当前位置能匹配上
                self.st[new_x][new_y] = 1
                if self.dfs(new_x, new_y, word[1:]):
                    return True
                self.st[new_x][new_y] = 0 # 回溯!! 释放当前位置
        return False
                

    def exist(self , board: List[str], word: str) -> bool:
        # write code here
        self.m, self.n = len(board), len(board[0])
        self.st = [[0] * self.n for _ in range(self.m)]
        self.board = board
        for i in range(self.m):
            for j in range(self.n):
                if board[i][j] == word[0]:
                    self.st[i][j] = 1
                    if self.dfs(i, j, word[1:]):
                        return True
                    self.st[i][j] = 0 # 回溯!! 释放当前位置
        return False