标签:
难度: Medium
标签:
难度: Medium
运行时间: 1470 ms
内存: 25.3 MB
from collections import deque from typing import List class Solution: def extractMantra(self, matrix: List[str], mantra: str) -> int: dq = deque([(0, 0, 0, 0)]) # (x, y, level, step) m,n,levelLength = len(matrix),len(matrix[0]),len(mantra) visited = [[[0]*n for _ in range(m)]for _ in range(levelLength)] while dq: x, y, level, step = dq.popleft() if level == levelLength: return step if matrix[x][y] == mantra[level]: dq.append((x, y, level + 1, step + 1)) else: for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: nx, ny = x + dx, y + dy if 0 <= nx < m and 0 <= ny < n and visited[level][nx][ny] != 1: dq.append((nx, ny, level, step + 1)) # 加在访问队列里了就标记,不然会重复加入访问队列 visited[level][nx][ny] = 1 return -1
该题解采用了宽度优先搜索(BFS)的策略来求解。首先,定义一个队列来存储探索状态,每个状态包含当前位置(x, y),当前正在尝试匹配的mantra中的字符索引(level),以及到达当前状态所需的步数(step)。整个矩阵的每个位置对应的每个字符索引都维护一个访问状态,以避免重复访问并陷入无限循环。从矩阵的左上角开始,对每个状态进行扩展:如果当前位置的字符与mantra中的当前字符匹配,则尝试移动到下一个字符,同时步数加一;否则,尝试向四个方向移动,每移动一步,步数也同样加一。这个过程持续进行,直到队列为空或成功匹配完所有字符。如果队列为空还未匹配完,返回-1表示无法完成提取。
时间复杂度: O(m*n*L)
空间复杂度: O(m*n*L)
from collections import deque from typing import List class Solution: def extractMantra(self, matrix: List[str], mantra: str) -> int: dq = deque([(0, 0, 0, 0)]) # (x, y, level, step) m,n,levelLength = len(matrix),len(matrix[0]),len(mantra) visited = [[[0]*n for _ in range(m)]for _ in range(levelLength)] # 访问状态数组 while dq: x, y, level, step = dq.popleft() # 取出当前状态 if level == levelLength: # 如果已匹配完所有字符 return step if matrix[x][y] == mantra[level]: # 当前位置字符匹配 dq.append((x, y, level + 1, step + 1)) # 移动到下一个字符 else: for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: # 探索四个方向 nx, ny = x + dx, y + dy if 0 <= nx < m and 0 <= ny < n and visited[level][nx][ny] != 1: dq.append((nx, ny, level, step + 1)) # 加入新状态到队列 visited[level][nx][ny] = 1 # 标记访问状态 return -1 # 无法完成提取
宽度优先搜索(BFS)适用于这种类型的问题,因为它按层次(逐级)探索所有可能的路径,从而确保找到的第一个解决方案是最短的路径。在尝试提取咒文的过程中,我们的目标是找到最小的步数,BFS可以在找到第一个匹配完整咒文的路径时立即停止搜索,保证这是最短的可行路径。相反,深度优先搜索(DFS)会探索完一个方向的所有可能性之后才会回溯,这可能导致它找到的是一个非最优解,而且效率较低,因为它可能探索很多不必要的路径。
访问状态数组是一个三维数组,每个元素代表一个特定字符在特定位置是否已经被访问过。具体地,第一维代表字符在咒文中的索引(level),第二维和第三维分别代表矩阵中的行(x)和列(y)。这样的设计是为了防止在搜索过程中重复访问相同的状态,从而避免无限循环并减少不必要的计算。通过记录每个字符索引在每个位置的访问状态,我们可以精确控制搜索过程,确保每个状态只被访问一次,提高算法效率。
为了处理位于矩阵边缘的格子并防止索引越界,题解中在尝试移动到新位置之前,会检查新的坐标(nx, ny)是否有效。具体的检查方法是确保nx和ny都在矩阵的有效范围内,即0 <= nx < m和0 <= ny < n,其中m和n分别是矩阵的行数和列数。只有当新的坐标在这个有效范围内时,才会继续执行移动和探索操作。这样的边界检查确保了算法的健壮性,避免了程序错误或崩溃。