请设计一个函数,用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。
知识点:递归与回溯
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程,最重要的就是查看能不能讲原本的问题分解为更小的子问题,这是使用递归的关键。
如果是线型递归,子问题直接回到父问题不需要回溯,但是如果是树型递归,父问题有很多分支,我需要从子问题回到父问题,进入另一个子问题。因此回溯是指在递归过程中,从某一分支的子问题回到父问题进入父问题的另一子问题分支,因为有时候进入第一个子问题的时候修改过一些变量,因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。
思路:要在矩阵中找到从某个位置开始,位置不重复的一条路径,路径为某个字符串,那我们肯定是现在矩阵中找到这个位置的起点。没办法直观的找出来,只能遍历矩阵每个位置都当作起点试一试。
找到起点后,它周围的节点是否可以走出剩余字符串子串的路径,该子问题又可以作为一个递归。因此,可以用递归来解决。
- 终止条件: 到了矩阵的边界或者是下一个字符与这个位置的字符不匹配,或者字符串匹配完成,都需要返回,
- 返回值: 将每条查询路径是否有这样的字符串返回,即true or false。
- 本级任务: 检查这个位置的字符与字符串中这个字符是否匹配,并向与它相邻的四个方向(且不是来的方向)延伸子问题。
class Solution:
def dfs(self, matrix: List[List[str]], n: int, m: int, i: int, j: int, word: str, k: int, flag: List[List[bool]]) -> bool:
if i < 0 or i >= n or j < 0 or j >= m or (matrix[i][j] != word[k]) or flag[i][j]:
#下标越界、字符不匹配、已经遍历过不能重复
return False
#k为记录当前第几个字符
if k == len(word) - 1:
return True
flag[i][j] = True
#该结点任意方向可行就可
if (self.dfs(matrix, n, m, i - 1, j, word, k + 1, flag)
or self.dfs(matrix, n, m, i + 1, j, word, k + 1, flag)
or self.dfs(matrix, n, m, i, j - 1, word, k + 1, flag)
or self.dfs(matrix, n, m, i , j + 1, word, k + 1, flag)):
return True
#没找到经过此格的,此格未被占用
flag[i][j] = False
return False
def hasPath(self , matrix: List[List[str]], word: str) -> bool:
if len(matrix) == 0:
return False
n = len(matrix)
m = len(matrix[0])
#初始化flag矩阵记录是否走过
flag = [[False for i in range (m)] for j in range(n)]
#遍历矩阵找起点
for i in range(n):
for j in range(m):
#通过dfs找到路径
if self.dfs(matrix, n, m, i, j, word, 0, flag):
return True
return False
复杂度分析:
- 时间复杂度:O(mn∗k3)O(mn*k^3)O(mn∗k3),其中mmm与nnn为矩阵的边长,kkk为字符串的长度,遍历一次矩阵,每次条递归最坏遍历深度为kkk,看起来是四个方向,但是有一个方向是来的方向不重复访问,所以是三叉树型递归,因此递归复杂度为O(k3)O(k^3)O(k3)
- 空间复杂度:O(mn)O(mn)O(mn),辅助二维数组记录是否走过某节点使用了空间



