题目
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
方法：回溯
- directs 定义移动的方向，分别为向上一格、向下一格、向右一格和向左一格
exist 函数： 判断 word 是否存在于网格 board 中
- m 表示网格 board 的行数，n 表示网格 board 的列数
- visited 记录某个网格是否已被使用，初始值均为 False
- 外部循环为对行的遍历，内部循环为对列的遍历
- 若某个格子的元素 board[i][j] 等于字符串的第一个元素 word[0]，那么将其设置为已被使用 visited[i][j] = True，并通过调用 traceback 函数判断其后面的元素 word[1:] 是否能够以此为原点通过上下左右移动被找到。若可以被找到，那么返回 True；否则，回溯，将该元素设置为未被使用 visited[i][j] = False，继续遍历
traceback 函数： 回溯，判断 word 某个字符是否可以通过上下左右移动一格找到
- m 表示网格 board 的行数，n 表示网格 board 的列数
- 判断 word 的长度，若长度为零，即已完成对 word 的遍历，那么返回 True
- 循环遍历移动的方向
- cur_i 和 cur_j 表示经历上下左右移动后的 i 和 j
- 若此时的 cur_i 大于等于零且小于行数，即 cur_i 值是合理的；cur_j 大于等于零且小于列数，即 cur_j 值是合理的；且此位置在网格中对应的元素 board[cur_i][cur_j] 和此时字符串的第一个元素 word[0] 相等：
- 根据题目同一个单元格内的字母不允许被重复使用，若该网格已被使用过，那么跳过此次循环
- 若该网格未被使用过，那么将此位置设置为已被使用
- 调用 traceback 函数判断 word 的下一个元素是否仍能能够通过上下左右移动而得到。若无法得到，则表示该网格点不是寻找的点，那么应该将该网格重新设置为未被使用
class Solution(object):
directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def exist(self, board, word):
m = len(board)
n = len(board[0])
visited = [[False] * n for row in range(m)]
for i in range(m):
for j in range(n):
if board[i][j] == word[0]:
visited[i][j] = True
if self.traceback(i, j, board, word[1:], visited):
return True
else:
visited[i][j] = False
return False
def traceback(self, i, j, board, word, visited):
m = len(board)
n = len(board[0])
if len(word) == 0:
return True
for direct in self.directs:
cur_i = i + direct[0]
cur_j = j + direct[1]
if cur_i >= 0 and cur_i < m and cur_j >= 0 and cur_j < n and board[cur_i][cur_j] == word[0]:
if visited[cur_i][cur_j]:
continue
visited[cur_i][cur_j] = True
if self.traceback(cur_i, cur_j, board, word[1:], visited):
return True
else:
visited[cur_i][cur_j] = False
return False
※ 两个回溯的作用：
网友评论