题目
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false
提示：
1 <= board.length <= 200
1 <= board[i].length <= 200
注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法
比较简单的回溯，我用了一个表来记录走过的路径，特别注意的是回溯到上一层的时候（函数结束）要还原回去。
还有用了一个全局变量来表示是否找到。
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
self.board = board
self.word_list = [c for c in word]
self.length = len(self.word_list)
self.ans = False
for i in range(len(self.board)):
for j in range(len(self.board[0])):
self.table = [[0]*len(self.board[0]) for _ in range(len(self.board))]
self.find(i,j,0)
if self.ans :
return True
return False
def find(self, i, j, str_index):
# 判读是否已成
if self.ans:
return
# 边界判断
if i < 0 or i >= len(self.board) or j < 0 or j >= len(self.board[0]) or self.table[i][j]==1:
return
if self.board[i][j] == self.word_list[str_index] :
# 可能是对的路
self.table[i][j] = 1
str_index += 1
# 完结
if str_index == self.length:
self.ans = True
return
# 继续走
self.find(i+1,j,str_index)
self.find(i,j+1,str_index)
self.find(i-1,j,str_index)
self.find(i,j-1,str_index)
self.table[i][j] = 0
总结
代码写得比较乱，但是总体思路没有问题。
需要整理。
来自leetcode精选题解的代码：
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(i, j, k):
if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False
if k == len(word) - 1: return True
tmp, board[i][j] = board[i][j], '/'
res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
board[i][j] = tmp
return res
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(i, j, 0): return True
return False
作者：jyd
链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/solution/mian-shi-ti-12-ju-zhen-zhong-de-lu-jing-shen-du-yo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
这个写得真简洁啊。
用board自身作为路径，不过访问过用'/'标记这个方法，在字符串中本身就有的话就不好使了。
所以根据以上的略改版本：
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
rows = len(board)
cols= len(board[0])
table = [[0]*cols for _ in range(rows)]
def dfs(i,j,index):
if not 0<=i<rows or not 0<=j<cols or board[i][j] != word[index] or table[i][j] == 1:
return False
# 这个容易忘记。。。
if index == len(word)-1:return True
table[i][j] = 1
ans = dfs(i+1,j,index+1) or dfs(i-1,j,index+1) or dfs(i,j+1,index+1) or dfs(i,j-1,index+1)
table[i][j] = 0
return ans
网友评论