我的代码如下:
class Solution:
def extractMantra(self, matrix: List[str], mantra: str) -> int:
m, n, L = len(matrix), len(matrix[0]), len(mantra)
pos = {} # 记录每个字母在矩阵中的所有位置
for i in range(m):
for j in range(n):
c = matrix[i][j]
if c in pos:
pos[c].append((i, j))
else:
pos[c] = [(i, j)]
MAX = float('inf')
dp = [[MAX] * n for _ in range(L + 1)]
for x, y in pos[mantra[0]]:
dp[1][y] = x # 初始化第一层状态
for i in range(2, L + 1):
for x, y in pos[mantra[i-1]]:
for prev_x, prev_y in pos[mantra[i-2]]:
dp[i][y] = min(dp[i][y], dp[i-1][prev_y] + abs(x-prev_x) + abs(y-prev_y))
return min(dp[L]) if min(dp[L]) < MAX else -1
求正确代码,有偿