Skip to main content

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
Last updated on by Kalkicode




Comment

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