Find length of the longest consecutive path from a given starting character in Python

We are going to Find the length of the longest consecutive path from a given starting character using Python.Let me first explain to you the problem and then the solution.

Here we will be given a matrix of alphabets and we have to find the longest consecutive path from a given character, where the path is in alphabetical order. Now let’s discuss the solution.

We can find a solution using various functions. Below are the code and its output.

Length of the longest consecutive path:

n = [[0 for i in range(c)] for i in range(r)]
def adjacent_check(prev, curr):
    if (ord(curr) - ord(prev)) == 1:
        return True
    return False
r = 3
c = 3
def valid_check(i, j):
    if (i < 0 or j < 0 or i >= r or j >= c):
        return False
    return True
x = [0, 1, 1, -1, 1, 0, -1, -1]
y = [1, 0, 1, 1, -1, -1, 0, -1]
def getLenUtility(m, i, j, prev):
    if (valid_check(i, j) == False or adjacent_check(prev, m[i][j]) == False):
        return 0
    if (n[i][j] != -1):
        return dp[i][j]
    ans = 0
    for k in range(8):
        ans = max(ans, 1 + getLenUtility(m, i + x[k], j + y[k], m[i][j]))
    n[i][j] = ans
    return n[i][j]
def getLength(m, s):
    for i in range(r):
        for j in range(c):
            n[i][j] = -1
    ans = 0
    for i in range(r):
        for j in range(c):
            if (m[i][j] == s):
               for k in range(8):
                    ans = max(ans, 1 + getLenUtility(m, i + x[k], j + y[k], s));
    return ans
m = [['a', 'b', 'c'],
       ['d', 'f', 'f'],
       ['g', 'h', 'i']]
print(getLength(m, 'g'))
print(getLength(m, 'c'))
print(getLength(m,'e'))

Output:

3
1
0

CODE EXPLAINATION:

In the above code, we have used two functions namely adjacent_check and valid_check to check the range of index and the consecutive path. For ‘g’, the length of the longest consecutive path is 3 because ‘g’ follows ‘h’ and in turn, ‘h’ follows ‘i’. I hope you enjoyed it. THANKYOU.