Posted on by Kalkicode
Code Matrix

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:

  1. a->b->b->a->a->b->b->a
  2. a->b->b->a->a->b->b->a
  3. a->b->b->a->a->b->b->a
  4. a->b->b->c->c->b->b->a
  5. a->a->b->c->c->b->a->a
  6. a->a->a->c->c->a->a->a
  7. 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

  1. Define a function palindrome that checks if a given array result[] from index start to index last is palindromic.
  2. Define a function palindrome_path that takes the matrix matrix[R][C], the array result[], the current row and col, the counter of elements visited, and the k 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.
  3. 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.

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.

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