CODEWITHSUNDEEP
arrayspython-3.xmatrixdata-structures
mlenthusiast
mlenthusiast

Reputation: 1204

Longest consecutive path in a matrix of letters

I'm trying to solve this problem:

Given a matrix of n * m, with letters(characters), find the longest consecutive path of letters in the matrix and output the string. For example:

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

result = e,f,g,h

You can only move up, down, left, right inside the matrix. This is what I have come up so far following some information online, but I'm not all the way there. I would also like to make the solution efficient, my current code might have too many loops and is probably slow for a large matrix. Any help would be really appreciated!

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

Upvotes: 0

Views: 316

Answers (1)

trincot
trincot

Reputation: 351288

Several issues in your code:

  • mat and matrix spelling should be unified.
  • s is never initialised
  • In R = len(matrix) and several other references to mat or matrix, that variable is not defined. findLongestSequence is called with the actual value of matrix, so it is there there R should be defined, ...etc

Also,

  • it is easier if you don't pass prev, but the actual expected character (that is already "incremented").
  • Why first initialise dp with zeroes, when then you re-initialise with -1? Just use -1 immediately.

Here is how it could work:

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)

Note that for this example data the returned answer is 8, not 4, as the longest sequence starts with "b" and ends with "i" -- 8 characters in total.

Upvotes: 1

Related Questions