时间戳

首页 > 解决方案 > 字母矩阵中最长的连续路径

arrays - 字母矩阵中最长的连续路径

问题描述

我正在尝试解决这个问题：

给定一个 n * m 的矩阵，包含字母（字符），找到矩阵中字母的最长连续路径并输出字符串。例如：

m = [[a,c,d],[i,b,e],[h,g,f]]

result = e,f,g,h

您只能在矩阵内上下左右移动。到目前为止，这是我根据网上的一些信息得出的结论，但我并不是一路走来。我还想让解决方案高效，我当前的代码可能有太多循环，并且对于大型矩阵可能很慢。任何帮助将非常感激！

R = len(matrix)
C = len(matrix[0])

x = [0, 1, 0, -1]
y = [1, 0, -1, 0]

dp=[[0 for i in range(C)]for i in range(R)]

def isvalid( i, j):
    if (i < 0 or j < 0 or i >= R or j >= C):
        return False
    return True

def getLenUtil(matrix, i, j, prev):
    if (isvalid(i, j)==False or isadjacent(prev, mat[i][j])==False):
        return 0
    if (dp[i][j] != -1):
        return dp[i][j]

    ans = 0

    for k in range(4):
        ans = max(ans, 1 + getLenUtil(mat, i + x[k],j + y[k], mat[i][j]))

    dp[i][j] = ans
    return dp[i][j]

def isadjacent(prev, curr):
    if (ord(curr) -ord(prev)) == 1:
        return True
    return False

def findLongestSequence(matrix):
    for i in range(R):
        for j in range(C):
            dp[i][j]=-1
    ans = 0
    for i in range(R):
        for j in range(C):
            if (mat[i][j] == s):
                for k in range(4):
                    ans = max(ans, 1 + getLenUtil(matrix, i + x[k], j + y[k], s));
     return ans

标签： arrayspython-3.xmatrixdata-structures

解决方案

您的代码中有几个问题：

  • mat并且matrix拼写要统一。
  • s从未初始化
  • 在R = len(matrix)和其他几个对mator的引用中matrix，未定义该变量。findLongestSequence用 的实际值调用matrix，所以应该在那里R定义，...等

还，

  • 如果您不通过prev，则更容易，但实际预期的字符（已经“增加”）。
  • 为什么先dp用零初始化，然后用-1重新初始化？立即使用 -1 。

以下是它的工作原理：

def findLongestSequence(mat):
    R = len(mat)
    C = len(mat[0])

    x = [0, 1, 0, -1]
    y = [1, 0, -1, 0]

    dp = [[-1 for i in range(C)] for i in range(R)]

    def isvalid( i, j):
        return (0 <= i < R) and (0 <= j < C)

    def getLenUtil(mat, i, j, expected):
        if not isvalid(i, j) or mat[i][j] != expected:
            return 0

        if dp[i][j] == -1:
            ans = 0
            expected = chr(ord(mat[i][j])+1)
            for k in range(4):
                ans = max(ans, 1 + getLenUtil(mat, i + x[k], j + y[k], expected))

            dp[i][j] = ans
        return dp[i][j]

    ans = 0
    for i in range(R):
        for j in range(C):
            getLenUtil(mat, i, j, mat[i][j])
        ans = max(ans, max(dp[i]))
    print(dp)
    return ans

res = findLongestSequence([["a","c","d"],["i","b","e"],["h","g","f"]])
print(res)

请注意，对于此示例数据，返回的答案是 8，而不是 4，因为最长的序列以“b”开头并以“i”结尾——总共 8 个字符。

推荐阅读