Menu Close

Return all palindromic paths of the matrix

Given a matrix containing lower alphabetical characters only, we need to print all palindromic paths in given matrix.
A path is defined as a sequence of cells starting from top-left cell and ending at bottom-right cell.
We are allowed to move to right and down only from current cell. We cannot go down diagonally.

Input: matrx[][] = {"aaab”, 
                   "baaa”
                   “abba”}

Output:
abaaba
aaaaaa
aaaaaa


Explanation :
aaaaaa (0, 0) -> (0, 1) -> (1, 1) -> 
       (1, 2) -> (1, 3) -> (2, 3)    
aaaaaa (0, 0) -> (0, 1) -> (0, 2) -> 
       (1, 2) -> (1, 3) -> (2, 3)    
abaaba (0, 0) -> (1, 0) -> (1, 1) -> 
       (1, 2) -> (2, 2) -> (2, 3)
def isPalin(str):
    temp=str[::-1]
    return 1 if temp==str else 0

def palindromicPath(str, a, i, j, m, n):
    if (j < n - 1 or i < m - 1) :
        if (i < m - 1):
            palindromicPath(str + a[i][j], a, i + 1, j, m, n)
        if (j < n - 1):
            palindromicPath(str + a[i][j], a, i, j + 1, m, n)
    else :
        str = str + a[m - 1][n - 1]
        if isPalin(str):
            print(str)

            
# Driver
Matrx = []
'''
Matrx = [[ 'a', 'a', 'a', 'b' ],
       ['b', 'a', 'a', 'a' ],
       [ 'a', 'b', 'b', 'a' ]]
'''
while True:
    arr=input("")
    if arr == "":
        break
    Matrx.append(list(arr))

str = ""
palindromicPath(str,Matrx, 0, 0, len(Matrx), len(Matrx[0]))

INPUT_1:
aaab
baaa
abba

OUTPUT:
abaaba
aaaaaa
aaaaaa

INPUT_2:
yyyy
xxxx
yyyy

OUTPUT:
yxxxxy
yyxxyy

ILLUSTRATION

Executed using Python3 in terminal Linux

Morae Q!