提取咒文

标签:

难度: Medium

随着兽群逐渐远去，一座大升降机缓缓的从地下升到了远征队面前。借由这台升降机，他们将能够到达地底的永恒至森。 在升降机的操作台上，是一个由魔法符号组成的矩阵，为了便于辨识，我们用小写字母来表示。 `matrix[i][j]` 表示矩阵第 `i` 行 `j` 列的字母。该矩阵上有一个提取装置，可以对所在位置的字母提取。 提取装置初始位于矩阵的左上角 `[0,0]`，可以通过每次操作移动到上、下、左、右相邻的 1 格位置中。提取装置每次移动或每次提取均记为一次操作。 远征队需要按照顺序，从矩阵中逐一取出字母以组成 `mantra`，才能够成功的启动升降机。请返回他们 **最少** 需要消耗的操作次数。如果无法完成提取，返回 `-1`。 **注意：** - 提取装置可对同一位置的字母重复提取，每次提取一个 - 提取字母时，需按词语顺序依次提取 **示例 1：** >输入：`matrix = ["sd","ep"], mantra = "speed"` > >输出：`10` > >解释：如下图所示 ![矩阵 (2).gif](https://pic.leetcode-cn.com/1646288670-OTlvAl-%E7%9F%A9%E9%98%B5%20\(2\).gif) **示例 2：** >输入：`matrix = ["abc","daf","geg"]， mantra = "sad"` > >输出：`-1` > >解释：矩阵中不存在 `s` ，无法提取词语 **提示：** - `0 < matrix.length, matrix[i].length <= 100` - `0 < mantra.length <= 100` - `matrix 和 mantra` 仅由小写字母组成

Submission

运行时间: 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

Explain

该题解采用了宽度优先搜索（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  # 无法完成提取

Explore

宽度优先搜索（BFS）适用于这种类型的问题，因为它按层次（逐级）探索所有可能的路径，从而确保找到的第一个解决方案是最短的路径。在尝试提取咒文的过程中，我们的目标是找到最小的步数，BFS可以在找到第一个匹配完整咒文的路径时立即停止搜索，保证这是最短的可行路径。相反，深度优先搜索（DFS）会探索完一个方向的所有可能性之后才会回溯，这可能导致它找到的是一个非最优解，而且效率较低，因为它可能探索很多不必要的路径。

访问状态数组是一个三维数组，每个元素代表一个特定字符在特定位置是否已经被访问过。具体地，第一维代表字符在咒文中的索引（level），第二维和第三维分别代表矩阵中的行（x）和列（y）。这样的设计是为了防止在搜索过程中重复访问相同的状态，从而避免无限循环并减少不必要的计算。通过记录每个字符索引在每个位置的访问状态，我们可以精确控制搜索过程，确保每个状态只被访问一次，提高算法效率。

为了处理位于矩阵边缘的格子并防止索引越界，题解中在尝试移动到新位置之前，会检查新的坐标（nx, ny）是否有效。具体的检查方法是确保nx和ny都在矩阵的有效范围内，即0 <= nx < m和0 <= ny < n，其中m和n分别是矩阵的行数和列数。只有当新的坐标在这个有效范围内时，才会继续执行移动和探索操作。这样的边界检查确保了算法的健壮性，避免了程序错误或崩溃。