Print all palindromic paths from top left to bottom right in a 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.
Example:
Input : mat[][] = {"aaab”, "baaa” “abba”} Output :aaaaaa, aaaaaa, abaaba 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)
Order of elements in the output array doesn’t matter.
The idea is simple. We start from top left (0, 0) and explore all paths to bottom right. If a path turns to be palindrome, we print it.
C++
Java
// Java program to print all palindromic paths // from top left to bottom right in a grid. public class PalinPath { public static boolean isPalin(String str) { int len = str.length() / 2 ; for ( int i = 0 ; i < len; i++) { if (str.charAt(i) != str.charAt(str.length() - i - 1 )) return false ; } return true ; } // i and j are row and column indexes of current cell // (initially these are 0 and 0). public static void palindromicPath(String str, char a[][], int i, int j, int m, int n) { // If we have not reached bottom right corner, keep // exploring if (j < m - 1 || i < n - 1 ) { if (i < n - 1 ) palindromicPath(str + a[i][j], a, i + 1 , j, m, n); if (j < m - 1 ) palindromicPath(str + a[i][j], a, i, j + 1 , m, n); } // If we reach bottom right corner, we check if // if the path used is palindrome or not. else { str = str + a[n - 1 ][m - 1 ]; if (isPalin(str)) System.out.println(str); } } // Driver code public static void main(String args[]) { char arr[][] = { { 'a' , 'a' , 'a' , 'b' }, { 'b' , 'a' , 'a' , 'a' }, { 'a' , 'b' , 'b' , 'a' } }; String str = "" ; palindromicPath(str, arr, 0 , 0 , 4 , 3 ); } } |
Python 3
# Python 3 program to print all # palindromic paths from top left # to bottom right in a grid. def isPalin( str ): l = len ( str ) / / 2 for i in range ( l) : if ( str [i] ! = str [ len ( str ) - i - 1 ]): return False return True # i and j are row and column # indexes of current cell # (initially these are 0 and 0). def palindromicPath( str , a, i, j, m, n): # If we have not reached bottom # right corner, keep exploring if (j < m - 1 or i < n - 1 ) : if (i < n - 1 ): palindromicPath( str + a[i][j], a, i + 1 , j, m, n) if (j < m - 1 ): palindromicPath( str + a[i][j], a, i, j + 1 , m, n) # If we reach bottom right corner, # we check if the path used is # palindrome or not. else : str = str + a[n - 1 ][m - 1 ] if isPalin( str ): print ( str ) # Driver code if __name__ = = "__main__" : arr = [[ 'a' , 'a' , 'a' , 'b' ], [ 'b' , 'a' , 'a' , 'a' ], [ 'a' , 'b' , 'b' , 'a' ]] str = "" palindromicPath( str , arr, 0 , 0 , 4 , 3 ) # This code is contributed # by ChitraNayal |
C#
// C# program to print all palindromic paths // from top left to bottom right in a grid. using System; class GFG { public static bool isPalin( string str) { int len = str.Length / 2; for ( int i = 0; i < len; i++) { if (str[i] != str[str.Length - i - 1]) { return false ; } } return true ; } // i and j are row and column indexes of // current cell (initially these are 0 and 0). public static void palindromicPath( string str, char [][] a, int i, int j, int m, int n) { // If we have not reached bottom // right corner, keep exploring if (j < m - 1 || i < n - 1) { if (i < n - 1) { palindromicPath(str + a[i][j], a, i + 1, j, m, n); } if (j < m - 1) { palindromicPath(str + a[i][j], a, i, j + 1, m, n); } } // If we reach bottom right corner, // we check if the path used is // palindrome or not. else { str = str + a[n - 1][m - 1]; if (isPalin(str)) { Console.WriteLine(str); } } } // Driver code public static void Main( string [] args) { char [][] arr = new char [][] { new char [] { 'a' , 'a' , 'a' , 'b' }, new char [] { 'b' , 'a' , 'a' , 'a' }, new char [] { 'a' , 'b' , 'b' , 'a' } }; string str = "" ; palindromicPath(str, arr, 0, 0, 4, 3); } } // This code is contributed by Shrikant13 |
Javascript
<script> // Javascript program to print // all palindromic paths // from top left to bottom // right in a grid. function isPalin(str) { let len = str.length / 2; for (let i = 0; i < len; i++) { if (str[i] != str[str.length - i - 1]) return false ; } return true ; } // i and j are row and column // indexes of current cell // (initially these are 0 and 0). function palindromicPath(str,a,i,j,m,n) { // If we have not reached bottom // right corner, keep // exploring if (j < m - 1 || i < n - 1) { if (i < n - 1) palindromicPath(str + a[i][j], a, i + 1, j, m, n); if (j < m - 1) palindromicPath(str + a[i][j], a, i, j + 1, m, n); } // If we reach bottom right corner, we check if // if the path used is palindrome or not. else { str = str + a[n - 1][m - 1]; if (isPalin(str)) document.write(str+ "<br>" ); } } // Driver code let arr = [[ 'a' , 'a' , 'a' , 'b' ], [ 'b' , 'a' , 'a' , 'a' ], [ 'a' , 'b' , 'b' , 'a' ]] let str = "" palindromicPath(str, arr, 0, 0, 4, 3) // This code is contributed by avanitrachhadiya2155 </script> |
Output :
abaaba aaaaaa aaaaaa
Contact Us