Print all palindromic paths from top left to bottom right
Given a matrix of size N x N, where each cell contains a lowercase English alphabet, the task is to print all the palindromic paths that can be formed from the top-left cell to the bottom-right cell. A palindromic path is defined as a path from the top-left to the bottom-right cell that reads the same forward and backward. A path can only move to the right, down, or diagonally right-down.
For example, consider the following matrix:
[
['a', 'a', 'a', 'b'],
['b', 'b', 'c', 'b'],
['b', 'b', 'c', 'a'],
['a', 'a', 'b', 'a'],
['a', 'b', 'b', 'a']
]
he palindromic paths that can be formed from the top-left cell to the bottom-right cell are:
a b b a a b b a
a b b a a b b a
a b b a a b b a
a b b c c b b a
a a b c c b a a
a a a c c a a a
a a a b b a a a
One possible solution approach to this problem is to use a recursive depth-first search (DFS) algorithm to explore all possible paths from the top-left cell to the bottom-right cell. At each step, we can check whether the current path is a palindrome or not. If it is, we can print it. If it is not, we can backtrack and try another path.
Code Solution
//C Program
//Print all palindromic paths from top left to bottom right
#include <stdio.h>
//size of matrix
#define R 5
#define C 4
//Function which is check palindromic path in given resultant array
int palindrome(char result[], int start, int last)
{
int status = 1;
while (start < last && status == 1)
{
if (result[start] != result[last])
{
//When two boundary elements are not same
status = 0;
}
start++;
last--;
}
return status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
void palindrome_path(char matrix[R][C],
char result[],
int row, int col,
int counter, int k)
{
if (row >= R || col >= C)
{
return;
}
//Get a new element of path
result[counter] = matrix[row][col];
palindrome_path(matrix, result, row + 1, col, counter + 1, k);
palindrome_path(matrix, result, row, col + 1, counter + 1, k);
//Check whether path contains k elements and
//path contains palindrome or not
if (counter + 1 == k && palindrome(result, 0, k - 1))
{
// When resultant path contains palindrome
// Display path elements
for (int i = 0; i < k; ++i)
{
printf("%3c", result[i]);
}
printf("\n");
}
}
int main()
{
char matrix[R][C] =
{
{'a', 'a', 'a', 'b'},
{'b', 'b', 'c', 'b'},
{'b', 'b', 'c', 'a'},
{'a', 'a', 'b', 'a'},
{'a', 'b', 'b', 'a'}
};
//Possible size of palindromic path
int size = R + C - 1;
//Auxiliary space which is used in stored the path of palindrome
char result[size];
palindrome_path(matrix, result, 0, 0, 0, size);
return 0;
}
Output
a b b a a b b a
a b b a a b b a
a b b a a b b a
a b b c c b b a
a a b c c b a a
a a a c c a a a
a a a b b a a a
/*
Java Program
Print all palindromic paths from top left to bottom right
*/
class MyMatrix
{
//Function which is check palindromic path in given resultant array
public boolean palindrome(char[] result, int start, int last)
{
boolean status = true;
while (start < last && status == true)
{
if (result[start] != result[last])
{
//When two boundary elements are not same
status = false;
}
start++;
last--;
}
return status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
public void palindrome_path(char[][] matrix, char[] result, int r, int c, int row_size, int col_size, int counter, int k)
{
if (r >= row_size || c >= col_size)
{
return;
}
//Get a new element of path
result[counter] = matrix[r][c];
palindrome_path(matrix, result, r + 1, c, row_size, col_size, counter + 1, k);
palindrome_path(matrix, result, r, c + 1, row_size, col_size, counter + 1, k);
//Check whether path contains k elements and
//path contains palindrome or not
if (counter + 1 == k && palindrome(result, 0, k - 1) == true)
{
// When resultant path contains palindrome
// Display path elements
for (int i = 0; i < k; ++i)
{
System.out.print(" " + result[i]);
}
System.out.print("\n");
}
}
public static void main(String[] args)
{
MyMatrix obj = new MyMatrix();
char[][] matrix = {
{'a', 'a', 'a', 'b'},
{'b', 'b', 'c', 'b'},
{'b', 'b', 'c', 'a'},
{'a', 'a', 'b', 'a'},
{'a', 'b', 'b', 'a'}
};
int row_size = matrix.length;
int col_size = matrix[0].length;
//Possible size of palindromic path
int size = row_size + col_size - 1;
//Auxiliary space which is used in stored the path of palindrome
char[] result = new char[size];
obj.palindrome_path(matrix, result, 0, 0, row_size, col_size, 0, size);
}
}
Output
a b b a a b b a
a b b a a b b a
a b b a a b b a
a b b c c b b a
a a b c c b a a
a a a c c a a a
a a a b b a a a
/*
C++ Program
Print all palindromic paths from top left to bottom right
*/
#include<iostream>
//size of matrix
#define R 5
#define C 4
using namespace std;
class MyMatrix
{
public:
//Function which is check palindromic path in given resultant array
bool palindrome(char *result, int start, int last)
{
bool status = true;
while (start < last && status == true)
{
if (result[start] != result[last])
{
//When two boundary elements are not same
status = false;
}
start++;
last--;
}
return status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
void palindrome_path(char matrix[R][C], char *result, int r, int c, int row_size, int col_size, int counter, int k)
{
if (r >= row_size || c >= col_size)
{
return;
}
//Get a new element of path
result[counter] = matrix[r][c];
this->palindrome_path(matrix, result, r + 1, c, row_size, col_size, counter + 1, k);
this->palindrome_path(matrix, result, r, c + 1, row_size, col_size, counter + 1, k);
//Check whether path contains k elements and
//path contains palindrome or not
if (counter + 1 == k && this->palindrome(result, 0, k - 1) == true)
{
// When resultant path contains palindrome
// Display path elements
for (int i = 0; i < k; ++i)
{
cout << " " << result[i];
}
cout << "\n";
}
}
};
int main()
{
MyMatrix obj = MyMatrix();
char matrix[R][C] = {
{
'a',
'a',
'a',
'b'
},
{
'b',
'b',
'c',
'b'
},
{
'b',
'b',
'c',
'a'
},
{
'a',
'a',
'b',
'a'
},
{
'a',
'b',
'b',
'a'
}
};
//Possible size of palindromic path
int size = R + C - 1;
char *result = new char[size];
obj.palindrome_path(matrix, result, 0, 0, R, C, 0, size);
return 0;
}
Output
a b b a a b b a
a b b a a b b a
a b b a a b b a
a b b c c b b a
a a b c c b a a
a a a c c a a a
a a a b b a a a
/*
C# Program
Print all palindromic paths from top left to bottom right
*/
using System;
class MyMatrix
{
//Function which is check palindromic path in given resultant array
public Boolean palindrome(char[] result, int start, int last)
{
Boolean status = true;
while (start < last && status == true)
{
if (result[start] != result[last])
{
//When two boundary elements are not same
status = false;
}
start++;
last--;
}
return status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
public void palindrome_path(char[,] matrix, char[] result, int r, int c, int row_size, int col_size, int counter, int k)
{
if (r >= row_size || c >= col_size)
{
return;
}
//Get a new element of path
result[counter] = matrix[r,c];
palindrome_path(matrix, result, r + 1, c, row_size, col_size, counter + 1, k);
palindrome_path(matrix, result, r, c + 1, row_size, col_size, counter + 1, k);
//Check whether path contains k elements and
//path contains palindrome or not
if (counter + 1 == k && palindrome(result, 0, k - 1) == true)
{
// When resultant path contains palindrome
// Display path elements
for (int i = 0; i < k; i++)
{
Console.Write(" " + result[i]);
}
Console.Write("\n");
}
}
public static void Main(String[] args)
{
MyMatrix obj = new MyMatrix();
char[,] matrix = {
{
'a',
'a',
'a',
'b'
},
{
'b',
'b',
'c',
'b'
},
{
'b',
'b',
'c',
'a'
},
{
'a',
'a',
'b',
'a'
},
{
'a',
'b',
'b',
'a'
}
};
int row_size = matrix.GetLength(0);
int col_size = matrix.GetLength(1);
//Possible size of palindromic path
int size = row_size + col_size - 1;
char[] result = new char[size];
obj.palindrome_path(matrix, result, 0, 0, row_size, col_size, 0, size);
}
}
Output
a b b a a b b a
a b b a a b b a
a b b a a b b a
a b b c c b b a
a a b c c b a a
a a a c c a a a
a a a b b a a a
<?php
/*
Php Program
Print all palindromic paths from top left to bottom right
*/
class MyMatrix
{
//Function which is check palindromic path in given resultant array
public function palindrome( & $result, $start, $last)
{
$status = true;
while ($start < $last && $status == true)
{
if ($result[$start] != $result[$last])
{
//When two boundary elements are not same
$status = false;
}
$start++;
$last--;
}
return $status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
public function palindrome_path( & $matrix, & $result, $r, $c, $row_size, $col_size, $counter, $k)
{
if ($r >= $row_size || $c >= $col_size)
{
return;
}
//Get a new element of path
$result[$counter] = $matrix[$r][$c];
$this->palindrome_path($matrix, $result, $r + 1, $c, $row_size, $col_size, $counter + 1, $k);
$this->palindrome_path($matrix, $result, $r, $c + 1, $row_size, $col_size, $counter + 1, $k);
//Check whether path contains k elements and
//path contains palindrome or not
if ($counter + 1 == $k && $this->palindrome($result, 0, $k - 1) == true)
{
// When resultant path contains palindrome
// Display path elements
for ($i = 0; $i < $k; ++$i)
{
echo(" ". $result[$i]);
}
echo("\n");
}
}
}
function main()
{
$obj = new MyMatrix();
$matrix = array(
array('a', 'a', 'a', 'b'),
array('b', 'b', 'c', 'b'),
array('b', 'b', 'c', 'a'),
array('a', 'a', 'b', 'a'),
array('a', 'b', 'b', 'a')
);
$row_size = count($matrix);
$col_size = count($matrix[0]);
//Possible size of palindromic path
$size = $row_size + $col_size - 1;
//Auxiliary space which is used in stored the path of palindrome
$result = array_fill(0, $size, ' ');
$obj->palindrome_path($matrix, $result, 0, 0, $row_size, $col_size, 0, $size);
}
main();
Output
a b b a a b b a
a b b a a b b a
a b b a a b b a
a b b c c b b a
a a b c c b a a
a a a c c a a a
a a a b b a a a
/*
Node Js Program
Print all palindromic paths from top left to bottom right
*/
class MyMatrix
{
//Function which is check palindromic path in given resultant array
palindrome(result, start, last)
{
var status = true;
while (start < last && status == true)
{
if (result[start] != result[last])
{
//When two boundary elements are not same
status = false;
}
start++;
last--;
}
return status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
palindrome_path(matrix, result, r, c, row_size, col_size, counter, k)
{
if (r >= row_size || c >= col_size)
{
return;
}
//Get a new element of path
result[counter] = matrix[r][c];
this.palindrome_path(matrix, result, r + 1, c, row_size, col_size, counter + 1, k);
this.palindrome_path(matrix, result, r, c + 1, row_size, col_size, counter + 1, k);
//Check whether path contains k elements and
//path contains palindrome or not
if (counter + 1 == k && this.palindrome(result, 0, k - 1) == true)
{
// When resultant path contains palindrome
// Display path elements
for (var i = 0; i < k; ++i)
{
process.stdout.write(" " + result[i]);
}
process.stdout.write("\n");
}
}
}
function main(args)
{
var obj = new MyMatrix();
var matrix = [
['a', 'a', 'a', 'b'],
['b', 'b', 'c', 'b'],
['b', 'b', 'c', 'a'],
['a', 'a', 'b', 'a'],
['a', 'b', 'b', 'a']
];
var row_size = matrix.length;
var col_size = matrix[0].length;
//Possible size of palindromic path
var size = row_size + col_size - 1;
//Auxiliary space which is used in stored the path of palindrome
var result = Array(size).fill(' ');
obj.palindrome_path(matrix, result, 0, 0, row_size, col_size, 0, size);
}
main();
Output
a b b a a b b a
a b b a a b b a
a b b a a b b a
a b b c c b b a
a a b c c b a a
a a a c c a a a
a a a b b a a a
# Ruby Program
# Print all palindromic paths from top left to bottom right
class MyMatrix
# Function which is check palindromic path in given resultant array
def palindrome(result, start, last)
status = true
while (start < last && status == true)
if (result[start] != result[last])
# When two boundary elements are not same
status = false
end
start += 1
last -= 1
end
return status
end
# Get all paths from top left to bottom right
# And display of all exist palindromic paths
def palindrome_path(matrix, result, r, c, row_size, col_size, counter, k)
if (r >= row_size || c >= col_size)
return
end
# Get a new element of path
result[counter] = matrix[r][c]
self.palindrome_path(matrix, result, r + 1, c, row_size, col_size, counter + 1, k)
self.palindrome_path(matrix, result, r, c + 1, row_size, col_size, counter + 1, k)
# Check whether path contains k elements and
# path contains palindrome or not
if (counter + 1 == k && self.palindrome(result, 0, k - 1) == true)
# When resultant path contains palindrome
# Display path elements
i = 0
while (i < k)
print(" ", result[i])
i += 1
end
print("\n")
end
end
end
def main()
obj = MyMatrix.new()
matrix = [
['a', 'a', 'a', 'b'],
['b', 'b', 'c', 'b'],
['b', 'b', 'c', 'a'],
['a', 'a', 'b', 'a'],
['a', 'b', 'b', 'a']
]
row_size = matrix.length
col_size = matrix[0].length
# Possible size of palindromic path
size = row_size + col_size - 1
result = Array.new(size, ' ')
obj.palindrome_path(matrix, result, 0, 0, row_size, col_size, 0, size)
end
main()
Output
a b b a a b b a
a b b a a b b a
a b b a a b b a
a b b c c b b a
a a b c c b a a
a a a c c a a a
a a a b b a a a
# Python 3 Program
# Print all palindromic paths from top left to bottom right
class MyMatrix :
# Function which is check palindromic path in given resultant array
def palindrome(self, result, start, last) :
status = True
while (start < last and status == True) :
if (result[start] != result[last]) :
# When two boundary elements are not same
status = False
start += 1
last -= 1
return status
# Get all paths from top left to bottom right
# And display of all exist palindromic paths
def palindrome_path(self, matrix, result, r, c, row_size, col_size, counter, k) :
if (r >= row_size or c >= col_size) :
return
# Get a new element of path
result[counter] = matrix[r][c]
self.palindrome_path(matrix, result, r + 1, c, row_size, col_size, counter + 1, k)
self.palindrome_path(matrix, result, r, c + 1, row_size, col_size, counter + 1, k)
# Check whether path contains k elements and
# path contains palindrome or not
if (counter + 1 == k and self.palindrome(result, 0, k - 1) == True) :
# When resultant path contains palindrome
# Display path elements
i = 0
while (i < k) :
print(" ", result[i], end = "")
i += 1
print("\n", end = "")
def main() :
obj = MyMatrix()
matrix = [
['a', 'a', 'a', 'b'],
['b', 'b', 'c', 'b'],
['b', 'b', 'c', 'a'],
['a', 'a', 'b', 'a'],
['a', 'b', 'b', 'a']
]
row_size = len(matrix)
col_size = len(matrix[0])
# Possible size of palindromic path
size = row_size + col_size - 1
result = [' '] * size
obj.palindrome_path(matrix, result, 0, 0, row_size, col_size, 0, size)
if __name__ == "__main__": main()
Output
a b b a a b b a
a b b a a b b a
a b b a a b b a
a b b c c b b a
a a b c c b a a
a a a c c a a a
a a a b b a a a
/*
Scala Program
Print all palindromic paths from top left to bottom right
*/
class MyMatrix
{
//Function which is check palindromic path in given resultant array
def palindrome(result: Array[Character], s: Int, e: Int): Boolean = {
var start = s;
var last = e;
var status: Boolean = true;
while (start < last && status == true)
{
if (result(start) != result(last))
{
//When two boundary elements are not same
status = false;
}
start += 1;
last -= 1;
}
return status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
def palindrome_path(matrix: Array[Array[Character]], result: Array[Character], r: Int, c: Int, row_size: Int, col_size: Int, counter: Int, k: Int): Unit = {
if (r >= row_size || c >= col_size)
{
return;
}
//Get a new element of path
result(counter) = matrix(r)(c);
palindrome_path(matrix, result, r + 1, c, row_size, col_size, counter + 1, k);
palindrome_path(matrix, result, r, c + 1, row_size, col_size, counter + 1, k);
//Check whether path contains k elements and
//path contains palindrome or not
if (counter + 1 == k && palindrome(result, 0, k - 1) == true)
{
// When resultant path contains palindrome
// Display path elements
var i: Int = 0;
while (i < k)
{
print(" " + result(i));
i += 1;
}
print("\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyMatrix = new MyMatrix();
var matrix: Array[Array[Character]] = Array(
Array('a', 'a', 'a', 'b'),
Array('b', 'b', 'c', 'b'),
Array('b', 'b', 'c', 'a'),
Array('a', 'a', 'b', 'a'),
Array('a', 'b', 'b', 'a')
);
var row_size: Int = matrix.length;
var col_size: Int = matrix(0).length;
//Possible size of palindromic path
var size: Int = row_size + col_size - 1;
var result: Array[Character] = Array.fill[Character](size)(' ');
obj.palindrome_path(matrix, result, 0, 0, row_size, col_size, 0, size);
}
}
Output
a b b a a b b a
a b b a a b b a
a b b a a b b a
a b b c c b b a
a a b c c b a a
a a a c c a a a
a a a b b a a a
/*
Swift Program
Print all palindromic paths from top left to bottom right
*/
class MyMatrix
{
//Function which is check palindromic path in given resultant array
func palindrome(_ result: [Character], _ s: Int, _ e: Int) -> Bool
{
var start = s;
var last = e;
var status: Bool = true;
while (start < last && status == true)
{
if (result[start] != result[last])
{
//When two boundary elements are not same
status = false;
}
start += 1;
last -= 1;
}
return status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
func palindrome_path(_ matrix: [[Character]], _ result: inout[Character], _ r: Int, _ c: Int, _ row_size: Int, _ col_size: Int, _ counter: Int, _ k: Int)
{
if (r >= row_size || c >= col_size)
{
return;
}
//Get a new element of path
result[counter] = matrix[r][c];
self.palindrome_path(matrix, &result, r + 1, c, row_size, col_size, counter + 1, k);
self.palindrome_path(matrix, &result, r, c + 1, row_size, col_size, counter + 1, k);
//Check whether path contains k elements and
//path contains palindrome or not
if (counter + 1 == k && self.palindrome(result, 0, k - 1) == true)
{
// When resultant path contains palindrome
// Display path elements
var i: Int = 0;
while (i < k)
{
print(" ", result[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
}
}
func main()
{
let obj: MyMatrix = MyMatrix();
let matrix: [
[Character]
] = [
["a", "a", "a", "b"],
["b", "b", "c", "b"],
["b", "b", "c", "a"],
["a", "a", "b", "a"],
["a", "b", "b", "a"]
];
let row_size: Int = matrix.count;
let col_size: Int = matrix[0].count;
//Possible size of palindromic path
let size: Int = row_size + col_size - 1;
var result: [Character] = Array(repeating: " ", count: size);
obj.palindrome_path(matrix, &result, 0, 0, row_size, col_size, 0, size);
}
main();
Output
a b b a a b b a
a b b a a b b a
a b b a a b b a
a b b c c b b a
a a b c c b a a
a a a c c a a a
a a a b b a a a
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment