Самый длинный последовательный путь в матрице букв - PullRequest
Новая
       41

Самый длинный последовательный путь в матрице букв

0 голосов
/ 20 декабря 2018

Я пытаюсь решить эту проблему:

Учитывая матрицу 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

1 Ответ

0 голосов
/ 20 декабря 2018

Несколько ошибок в вашем коде:

  • mat и matrix орфография должна быть унифицирована.
  • s никогда не инициализируется
  • In R = len(matrix) и несколько других ссылок на mat или 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 символов.

...