Print all palindromic paths from top left to bottom right
The problem involves finding and printing all palindromic paths from the top left corner of a given matrix to the bottom right corner. A palindromic path is a sequence of elements in the matrix that reads the same from left to right and from top to bottom.
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
The palindromic paths in this matrix 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
Idea to Solve the Problem
To find all palindromic paths, we need to explore all possible paths from the top left corner to the bottom right corner of the matrix. While traversing the paths, we need to keep track of the elements visited so far and check if the current path is palindromic. If it is, we print the path.
Algorithm
- Define a function
palindrome
that checks if a given arrayresult[]
from indexstart
to indexlast
is palindromic. - Define a function
palindrome_path
that takes the matrixmatrix[R][C]
, the arrayresult[]
, the currentrow
andcol
, thecounter
of elements visited, and thek
value (size of the path) as parameters.- If the current row or column is out of bounds, return.
- Add the current element of the matrix to the
result[]
array. - Recursively call
palindrome_path
for the next row or column. - If the current path contains
k
elements and is palindromic, print the path elements.
- In the
main
function:- Define the matrix
matrix[R][C]
. - Calculate the maximum size of a palindromic path (sum of rows and columns - 1).
- Define an array
result[]
to store the path. - Call the
palindrome_path
function with initial parameters.
- Define the matrix
Pseudocode
palindrome(start, last, result):
status = 1
while start < last and status == 1:
if result[start] is not equal to result[last]:
set status to 0
increment start and decrement last
return status
palindrome_path(matrix, result, row, col, counter, k):
if row >= R or col >= C:
return
add matrix[row][col] to result at index counter
call palindrome_path with row+1, col, counter+1, k
call palindrome_path with row, col+1, counter+1, k
if counter+1 is equal to k and palindrome(result, 0, k-1):
loop through i from 0 to k-1:
print result[i]
print a newline
main:
matrix = ... // Define the matrix
calculate maximum path size and store in size
define result array of size size
call palindrome_path with matrix, result, 0, 0, 0, size
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
Output Explanation
The mentioned C code implements the above algorithm to find and print all palindromic paths in the given matrix. It explores all possible paths and checks if each path is palindromic. If a palindromic path is found, it prints the path elements.
Time Complexity
The time complexity of the algorithm depends on the number of paths explored and the time complexity of the
palindrome
function. In the worst case, the algorithm explores all paths from the top left to the
bottom right corner, which is exponential. Additionally, the palindrome
function takes O(k) time to
check if a path is palindromic, where k is the size of the path. Therefore, the overall time complexity can be
considered as O(2^(R+C)) * O(k), where R is the number of rows, C is the number of columns, and k is the maximum
path size.
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