189 8069 5689
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
class Solution:
"""
判断迷宫/棋盘内是否有解的一个方法是回溯法。
当位于坐标(i, j)的时候，如果当前位置有效，则往所有可能的方向都走一步，否则回退到上一步
回溯一般可以基于递归或栈来实现。
以递归为例，若当前位置合法(未被剪枝去掉)，则从当前位置出发，继续探索可能的位置，否则回退到
上一个位置
"""
def hasPath(self, matrix, path):
def helper(path_, row, col):
"""
由(row, col)出发，探索所有可能的位置(递)，
当发现有解或需要剪枝的时候就返回上一步(归)
:param path_: 剩余待查找的路径
:param row: 当前所在的行
:param col:当前所在的列
:return: 是否有解
"""
if not path_:
return True
if (row >= rows or row < 0 or col >= cols or col < 0
or matrix[row][col] != path_[0]):
return False
temp = matrix[row][col] # 记录当前位置的值，以便回溯的时候还原
matrix[row][col] = '#' # 标记为已走过
# 探索左右可能的位置(子节点)
res = (helper(path_[1:], row, col + 1)
or helper(path_[1:], row, col - 1)
or helper(path_[1:], row + 1, col)
or helper(path_[1:], row - 1, col))
matrix[row][col] = temp # 回溯时还原前面的标记，因为回溯后这个点相当于没走过
return res
if not path:
return True
if not matrix:
return False
rows, cols = len(matrix), len(matrix[0])
for i in range(rows):
for j in range(cols):
# 这里可以先判断是否符合起点再进行递归也可以直接递归，但是先判断可以减少开销
if matrix[i][j] == path[0]:
if helper(path, i, j):
return True
return False另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。