Posted on by Kalkicode
Code Dynamic Programming

Count number of palindromic path in a matrix

In this article, we will explore a Java program to count the number of palindromic paths in a given matrix. A palindromic path is a path in the matrix that forms a palindrome, meaning it reads the same forwards and backwards. We will provide a problem statement, present a detailed algorithm with explanations, and demonstrate the expected output of the program. Additionally, we will discuss the time complexity of the code.

Problem Statement

Given a matrix containing characters, we need to count the number of palindromic paths that can be formed using the elements of the matrix. A path can start from any cell and can move in any of the four directions: up, down, left, or right. The path can only move to a neighboring cell if the characters in the current and neighboring cells are the same. Our goal is to find the count of all such palindromic paths in the matrix.

Algorithm

  1. We start by defining a class called "Coordinates" to represent the coordinates of a path in the matrix. It consists of the starting column (sc), ending column (ec), starting row (sr), and ending row (er).
  2. We create a class named "PalindromicPath" that contains the main logic for counting the palindromic paths.
  3. Inside the "PalindromicPath" class, we define a method called absValue to calculate the absolute value of a number.
  4. We create a method named countPath that takes the matrix, a hashmap to store intermediate results (dp), and the starting and ending coordinates of a path.
  5. We check for boundary conditions: if the coordinates are out of range or if there is an overlap in the path. In such cases, we return 0.
  6. If the characters at the start and end coordinates are not the same, we return 0 as well since a palindrome cannot be formed.
  7. If the absolute difference between the starting row and ending row plus the starting column and ending column is less than or equal to 1, we have a palindromic path of length 1. In this case, we return 1.
  8. Next, we create an instance of the "Coordinates" class with the provided coordinates.
  9. We check if the hashmap already contains the current coordinates. If it does, we retrieve the count and return it.
  10. If the coordinates are new, we recursively calculate the count of palindromic paths by making four recursive calls:
    • Moving down and up: countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m)
    • Moving left and down: countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m)
    • Moving right and up: countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m)
    • Moving right and down: countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m)
  11. We add up the counts obtained from these recursive calls.
  12. Finally, we store the count in the hashmap and return it.
  13. In the main function, we create an instance of the "PalindromicPath" class.
  14. We define a sample matrix and pass it to the countPalindromicPath method.
  15. The result is printed on the console.

Code Solution

import java.util.HashMap;
/*
    Java Program for
    Count number of palindromic path in a matrix
*/
class Coordinates
{
	public int sc;
	public int ec;
	public int sr;
	public int er;
	public Coordinates(int sc, int ec, int sr, int er)
	{
		this.sc = sc;
		this.ec = ec;
		this.sr = sr;
		this.er = er;
	}
}
public class PalindromicPath
{
	public int absValue(int value)
	{
		if (value < 0)
		{
			return -value;
		}
		return value;
	}
	public int countPath(char[][] matrix, HashMap < Coordinates, Integer > dp, int sc, int ec, int sr, int er, int n, int m)
	{
		if (sc < 0 || ec < 0 || sr < 0 || er < 0 || 
            sc >= m || ec >= m || sr >= n || er >= n)
		{
			// When index are out of range
			return 0;
		}
		if (sc > ec || sr > er)
		{
			// Overlapping case
			return 0;
		}
		else if (matrix[er][ec] != matrix[sr][sc])
		{
			// When palindrome not exist in given indexes
			return 0;
		}
		else if (absValue((sr - er) + (sc - ec)) <= 1)
		{
			return 1;
		}
		Coordinates point = new Coordinates(sc, ec, sr, er);
		if (dp.containsKey(point))
		{
			// When point already exists
			return dp.get(point);
		}
		// Calculate palindromic path using recursion
		int count = countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m) + 
          countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m) + 
          countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m) + 
          countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m);
		dp.put(point, count);
		return count;
	}
	// This function are handling the request of counting palindromic path.
	public void countPalindromicPath(char[][] matrix)
	{
		// Get the length
		int n = matrix.length;
		int m = matrix[0].length;
		// Manage coordinates points
		HashMap < Coordinates, Integer > dp = 
          new HashMap < Coordinates, Integer > ();
		int result = countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m);
		System.out.print("\n Result : " + result);
	}
	public static void main(String[] args)
	{
		PalindromicPath task = new PalindromicPath();
		char[][] matrix = {
			{
				'a' , 'a' , 'a' , 'b'
			},
			{
				'b' , 'b' , 'c' , 'b'
			},
			{
				'b' , 'b' , 'c' , 'a'
			},
			{
				'a' , 'a' , '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  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
		    --------------------------
		    Result = 7
		*/
		task.countPalindromicPath(matrix);
	}
}

Output

 Result :  7
// Include header file
#include <iostream>
#include <unordered_map>
#define N 5
#define M 4
using namespace std;
/*
    C++ Program for
    Count number of palindromic path in a matrix
*/
class Coordinates
{
    public: int sc;
    int ec;
    int sr;
    int er;
    Coordinates(int sc, int ec, int sr, int er)
    {
        this->sc = sc;
        this->ec = ec;
        this->sr = sr;
        this->er = er;
    }
};
class PalindromicPath
{
    public: int absValue(int value)
    {
        if (value < 0)
        {
            return -value;
        }
        return value;
    }
    int countPath(
        char matrix[N][M], 
        unordered_map <Coordinates*, int > &dp, 
        int sc, 
        int ec, 
        int sr, 
        int er)
    {
        if (sc < 0 || ec < 0 || sr < 0 || er < 0 || sc >= M || 
            ec >= M || sr >= N || er >= N)
        {
            // When index are out of range
            return 0;
        }
        if (sc > ec || sr > er)
        {
            // Overlapping case
            return 0;
        }
        else if (matrix[er][ec] != matrix[sr][sc])
        {
            // When palindrome not exist in given indexes
            return 0;
        }
        else if (this->absValue((sr - er) + (sc - ec)) <= 1)
        {
            return 1;
        }
        Coordinates *point = new Coordinates(sc, ec, sr, er);
        if (dp.find(point) != dp.end())
        {
            // When point already exists
            return dp[point];
        }
        // Calculate palindromic path using recursion
        int count = this->countPath(matrix, dp, sc, ec, sr + 1, er - 1) + 
        this->countPath(matrix, dp, sc, ec - 1, sr + 1, er) + 
        this->countPath(matrix, dp, sc + 1, ec, sr, er - 1) + 
        this->countPath(matrix, dp, sc + 1, ec - 1, sr, er);
        dp[point] = count;
        return count;
    }
    // This function are handling the request of counting palindromic path.
    void countPalindromicPath(char matrix[N][M])
    {
        // Manage coordinates points
        unordered_map <Coordinates*, int > dp;
        int result = this->countPath(matrix, dp, 0, M - 1, 0, N - 1);
        cout << "\n Result : " << result;
    }
};
int main()
{
    PalindromicPath *task = new PalindromicPath();
    char matrix[N][M] = {
        {
            'a' , 'a' , 'a' , 'b'
        } , {
            'b' , 'b' , 'c' , 'b'
        } , {
            'b' , 'b' , 'c' , 'a'
        } , {
            'a' , 'a' , '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  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
        --------------------------
        Result = 7
    */
    task->countPalindromicPath(matrix);
    return 0;
}

Output

 Result : 7
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp Program for
    Count number of palindromic path in a matrix
*/
public class Coordinates
{
	public int sc;
	public int ec;
	public int sr;
	public int er;
	public Coordinates(int sc, int ec, int sr, int er)
	{
		this.sc = sc;
		this.ec = ec;
		this.sr = sr;
		this.er = er;
	}
}
public class PalindromicPath
{
	public int absValue(int value)
	{
		if (value < 0)
		{
			return -value;
		}
		return value;
	}
	public int countPath(
  	char[,] matrix, 
 	Dictionary < Coordinates, int > dp, 
    int sc, int ec, int sr, int er, int n, int m)
	{
		if (sc < 0 || ec < 0 || sr < 0 || er < 0 || 
            sc >= m || ec >= m || sr >= n || er >= n)
		{
			// When index are out of range
			return 0;
		}
		if (sc > ec || sr > er)
		{
			// Overlapping case
			return 0;
		}
		else if (matrix[er,ec] != matrix[sr,sc])
		{
			// When palindrome not exist in given indexes
			return 0;
		}
		else if (this.absValue((sr - er) + (sc - ec)) <= 1)
		{
			return 1;
		}
		Coordinates point = new Coordinates(sc, ec, sr, er);
		if (dp.ContainsKey(point))
		{
			// When point already exists
			return dp[point];
		}
		// Calculate palindromic path using recursion
		int count = this.countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m) + 
          this.countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m) + 
          this.countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m) + 
          this.countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m);
		dp.Add(point, count);
		return count;
	}
	// This function are handling the request of counting palindromic path.
	public void countPalindromicPath(char[,] matrix)
	{
		// Get the length
		int n = matrix.GetLength(0);
		int m = matrix.GetLength(1);
		// Manage coordinates points
		Dictionary < Coordinates, int > dp = 
          new Dictionary < Coordinates, int > ();
		int result = this.countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m);
		Console.Write("\n Result : " + result);
	}
	public static void Main(String[] args)
	{
		PalindromicPath task = new PalindromicPath();
		char[,] matrix = {
			{
				'a' , 'a' , 'a' , 'b'
			},
			{
				'b' , 'b' , 'c' , 'b'
			},
			{
				'b' , 'b' , 'c' , 'a'
			},
			{
				'a' , 'a' , '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  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
		    --------------------------
		    Result = 7
		*/
		task.countPalindromicPath(matrix);
	}
}

Output

 Result : 7
package main
import "fmt"
/*
    Go Program for
    Count number of palindromic path in a matrix
*/
type Coordinates struct {
	sc int
	ec int
	sr int
	er int
}
func getCoordinates(sc int, ec int, sr int, er int) * Coordinates {
	var me *Coordinates = &Coordinates {}
	me.sc = sc
	me.ec = ec
	me.sr = sr
	me.er = er
	return me
}
type PalindromicPath struct {}
func getPalindromicPath() * PalindromicPath {
	var me *PalindromicPath = &PalindromicPath {}
	return me
}
func(this PalindromicPath) absValue(value int) int {
	if value < 0 {
		return -value
	}
	return value
}
func(this PalindromicPath) countPath(matrix[][] byte, 
	dp map[*Coordinates] int, sc int, ec int, 
	sr int, er int, n int, m int) int {
	if sc < 0 || ec < 0 || sr < 0 || er < 0 || sc >= m || 
		ec >= m || sr >= n || er >= n {
		// When index are out of range
		return 0
	}
	if sc > ec || sr > er {
		// Overlapping case
		return 0
	} else if matrix[er][ec] != matrix[sr][sc] {
		// When palindrome not exist in given indexes
		return 0
	} else if this.absValue((sr - er) + (sc - ec)) <= 1 {
		return 1
	}
	var point * Coordinates = getCoordinates(sc, ec, sr, er)
	if _, found := dp[point] ; found {
		// When point already exists
		return dp[point]
	}
	// Calculate palindromic path using recursion
	var count int = this.countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m) + 
	this.countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m) + 
	this.countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m) + 
	this.countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m)
	dp[point] = count
	return count
}
// This function are handling the request of counting palindromic path.
func(this PalindromicPath) countPalindromicPath(matrix[][] byte) {
	// Get the length
	var n int = len(matrix)
	var m int = len(matrix[0])
	// Manage coordinates points
	var dp = make(map[*Coordinates] int)
	var result int = this.countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m)
	fmt.Print("\n Result : ", result)
}
func main() {
	var task * PalindromicPath = getPalindromicPath()
	var matrix = [][] byte {
		{'a', 'a', 'a', 'b'}, 
        {'b', 'b', 'c', 'b'}, 
        {'b', 'b', 'c', 'a'},
        {'a', 'a', '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  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
	    --------------------------
	    Result = 7
	*/
	task.countPalindromicPath(matrix)
}

Output

 Result : 7
<?php
/*
    Php Program for
    Count number of palindromic path in a matrix
*/
class Coordinates
{
	public $sc;
	public $ec;
	public $sr;
	public $er;
	public	function __construct($sc, $ec, $sr, $er)
	{
		$this->sc = $sc;
		$this->ec = $ec;
		$this->sr = $sr;
		$this->er = $er;
	}
  	public function getValue()
  	{
      	return $this->sc."-".$this->ec."-".$this->sr."-".$this->er;
  	}
}
class PalindromicPath
{
	public	function absValue($value)
	{
		if ($value < 0)
		{
			return -$value;
		}
		return $value;
	}
	public	function countPath($matrix, &$dp, $sc, $ec, $sr, $er, $n, $m)
	{
		if ($sc < 0 || $ec < 0 || $sr < 0 || $er < 0 || 
            $sc >= $m || $ec >= $m || $sr >= $n || $er >= $n)
		{
			// When index are out of range
			return 0;
		}
		if ($sc > $ec || $sr > $er)
		{
			// Overlapping case
			return 0;
		}
		else if ($matrix[$er][$ec] != $matrix[$sr][$sc])
		{
			// When palindrome not exist in given indexes
			return 0;
		}
		else if ($this->absValue(($sr - $er) + ($sc - $ec)) <= 1)
		{
			return 1;
		}
		$point = new Coordinates($sc, $ec, $sr, $er);
		if (array_key_exists("'".$point->getValue()."'", $dp))
		{
			// When point already exists
			return $dp["'".$point->getValue()."'"];
		}
		// Calculate palindromic path using recursion
		$count = 
          $this->countPath($matrix, $dp, $sc, $ec, $sr + 1, $er - 1, $n, $m) + 
          $this->countPath($matrix, $dp, $sc, $ec - 1, $sr + 1, $er, $n, $m) +
          $this->countPath($matrix, $dp, $sc + 1, $ec, $sr, $er - 1, $n, $m) + 
          $this->countPath($matrix, $dp, $sc + 1, $ec - 1, $sr, $er, $n, $m);
		  $dp["'".$point->getValue()."'"] = $count;
		return $count;
	}
	// This function are handling the request of counting palindromic path.
	public	function countPalindromicPath($matrix)
	{
		// Get the length
		$n = count($matrix);
		$m = count($matrix[0]);
		// Manage coordinates points
		$dp = array();
		$result = $this->countPath($matrix, $dp, 0, $m - 1, 0, $n - 1, $n, $m);
		echo("\n Result : ".$result);
	}
}

function main()
{
	$task = new PalindromicPath();
	$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')
    );
	/*
	    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
	    --------------------------
	    Result = 7
	*/
	$task->countPalindromicPath($matrix);
}
main();

Output

 Result : 7
/*
    Node JS Program for
    Count number of palindromic path in a matrix
*/
class Coordinates
{
	constructor(sc, ec, sr, er)
	{
		this.sc = sc;
		this.ec = ec;
		this.sr = sr;
		this.er = er;
	}
}
class PalindromicPath
{
	absValue(value)
	{
		if (value < 0)
		{
			return -value;
		}
		return value;
	}
	countPath(matrix, dp, sc, ec, sr, er, n, m)
	{
		if (sc < 0 || ec < 0 || sr < 0 || er < 0 || 
            sc >= m || ec >= m || sr >= n || er >= n)
		{
			// When index are out of range
			return 0;
		}
		if (sc > ec || sr > er)
		{
			// Overlapping case
			return 0;
		}
		else if (matrix[er][ec] != matrix[sr][sc])
		{
			// When palindrome not exist in given indexes
			return 0;
		}
		else if (this.absValue((sr - er) + (sc - ec)) <= 1)
		{
			return 1;
		}
		var point = new Coordinates(sc, ec, sr, er);
		if (dp.has(point))
		{
			// When point already exists
			return dp.get(point);
		}
		// Calculate palindromic path using recursion
		var count = this.countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m) + 
            this.countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m) + 
            this.countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m) + 
            this.countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m);
		dp.set(point, count);
		return count;
	}
	// This function are handling the request of counting palindromic path.
	countPalindromicPath(matrix)
	{
		// Get the length
		var n = matrix.length;
		var m = matrix[0].length;
		// Manage coordinates points
		var dp = new Map();
		var result = this.countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m);
		process.stdout.write("\n Result : " + result);
	}
}

function main()
{
	var task = new PalindromicPath();
	var matrix = [
		['a', 'a', 'a', 'b'],
		['b', 'b', 'c', 'b'],
		['b', 'b', 'c', 'a'],
		['a', 'a', '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  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
	    --------------------------
	    Result = 7
	*/
	task.countPalindromicPath(matrix);
}
main();

Output

 Result : 7
#    Python 3 Program for
#    Count number of palindromic path in a matrix
class Coordinates :
	def __init__(self, sc, ec, sr, er) :
		self.sc = sc
		self.ec = ec
		self.sr = sr
		self.er = er
	

class PalindromicPath :
	def absValue(self, value) :
		if (value < 0) :
			return -value
		
		return value
	
	def countPath(self, matrix, dp, sc, ec, sr, er, n, m) :
		if (sc < 0 or ec < 0 or sr < 0 or er < 0 or sc >= m or 
            ec >= m or sr >= n or er >= n) :
			#  When index are out of range
			return 0
		
		if (sc > ec or sr > er) :
			#  Overlapping case
			return 0
		elif (matrix[er][ec] != matrix[sr][sc]) :
			#  When palindrome not exist in given indexes
			return 0
		elif (self.absValue((sr - er) + (sc - ec)) <= 1) :
			return 1
		
		point = Coordinates(sc, ec, sr, er)
		if ((point in dp.keys())) :
			#  When point already exists
			return dp.get(point)
		
		#  Calculate palindromic path using recursion
		count = self.countPath(
          matrix, dp, sc, ec, sr + 1, er - 1, n, m
        ) + self.countPath(
          matrix, dp, sc, ec - 1, sr + 1, er, n, m
        ) + self.countPath(
          matrix, dp, sc + 1, ec, sr, er - 1, n, m
        ) + self.countPath(
          matrix, dp, sc + 1, ec - 1, sr, er, n, m
        )
		dp[point] = count
		return count
	
	#  This function are handling the request of counting palindromic path.
	def countPalindromicPath(self, matrix) :
		#  Get the length
		n = len(matrix)
		m = len(matrix[0])
		#  Manage coordinates points
		dp = dict()
		result = self.countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m)
		print("\n Result : ", result, end = "")
	

def main() :
	task = PalindromicPath()
	matrix = [
		['a', 'a', 'a', 'b'],
		['b', 'b', 'c', 'b'],
		['b', 'b', 'c', 'a'],
		['a', 'a', '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  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
	#    --------------------------
	#    Result = 7
	task.countPalindromicPath(matrix)

if __name__ == "__main__": main()

Output

 Result :  7
#    Ruby Program for
#    Count number of palindromic path in a matrix
class Coordinates 
	# Define the accessor and reader of class Coordinates
	attr_reader :sc, :ec, :sr, :er
	attr_accessor :sc, :ec, :sr, :er
	def initialize(sc, ec, sr, er) 
		self.sc = sc
		self.ec = ec
		self.sr = sr
		self.er = er
	end

end

class PalindromicPath 
	def absValue(value) 
		if (value < 0) 
			return -value
		end

		return value
	end

	def countPath(matrix, dp, sc, ec, sr, er, n, m) 
		if (sc < 0 || ec < 0 || sr < 0 || er < 0 || 
            sc >= m || ec >= m || sr >= n || er >= n) 
			#  When index are out of range
			return 0
		end

		if (sc > ec || sr > er) 
			#  Overlapping case
			return 0
		elsif (matrix[er][ec] != matrix[sr][sc]) 
			#  When palindrome not exist in given indexes
			return 0
		elsif (self.absValue((sr - er) + (sc - ec)) <= 1) 
			return 1
		end

		point = Coordinates.new(sc, ec, sr, er)
		if (dp.key?(point)) 
			#  When point already exists
			return dp[point]
		end

		#  Calculate palindromic path using recursion
		count = self.countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m) + 
          self.countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m) + 
          self.countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m) + 
          self.countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m)
		dp[point] = count
		return count
	end

	#  This function are handling the request of counting palindromic path.
	def countPalindromicPath(matrix) 
		#  Get the length
		n = matrix.length
		m = matrix[0].length
		#  Manage coordinates points
		dp = Hash.new()
		result = self.countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m)
		print("\n Result : ", result)
	end

end

def main() 
	task = PalindromicPath.new()
	matrix = [
		['a', 'a', 'a', 'b'],
		['b', 'b', 'c', 'b'],
		['b', 'b', 'c', 'a'],
		['a', 'a', '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  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
	#    --------------------------
	#    Result = 7
	task.countPalindromicPath(matrix)
end

main()

Output

 Result : 7
import scala.collection.mutable._;
/*
    Scala Program for
    Count number of palindromic path in a matrix
*/
class Coordinates(var sc: Int,
	var ec: Int,
    var sr: Int,
	var er: Int);
class PalindromicPath()
{
	def absValue(value: Int): Int = {
		if (value < 0)
		{
			return -value;
		}
		return value;
	}
	def countPath(matrix: Array[Array[Char]], 
      dp: HashMap[Coordinates, Int], 
        sc: Int, ec: Int, sr: Int, 
        er: Int, n: Int, m: Int): Int = {
		if (sc < 0 || ec < 0 || sr < 0 || er < 0 || 
             sc >= m || ec >= m || sr >= n || er >= n)
		{
			// When index are out of range
			return 0;
		}
		if (sc > ec || sr > er)
		{
			// Overlapping case
			return 0;
		}
		else if (matrix(er)(ec) != matrix(sr)(sc))
		{
			// When palindrome not exist in given indexes
			return 0;
		}
		else if (absValue((sr - er) + (sc - ec)) <= 1)
		{
			return 1;
		}
		var point: Coordinates = new Coordinates(sc, ec, sr, er);
		if (dp.contains(point))
		{
			// When point already exists
			return dp.get(point).get;
		}
		// Calculate palindromic path using recursion
		var count: Int = countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m) + 
          countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m) + 
          countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m) + 
          countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m);
		dp.addOne(point, count);
		return count;
	}
	// This function are handling the request of counting palindromic path.
	def countPalindromicPath(matrix: Array[Array[Char]]): Unit = {
		// Get the length
		var n: Int = matrix.length;
		var m: Int = matrix(0).length;
		// Manage coordinates points
		var dp: HashMap[Coordinates, Int] = new HashMap[Coordinates, Int]();
		var result: Int = countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m);
		print("\n Result : " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: PalindromicPath = new PalindromicPath();
		var matrix: Array[Array[Char]] = 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')
        );
		/*
		    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
		    --------------------------
		    Result = 7
		*/
		task.countPalindromicPath(matrix);
	}
}

Output

 Result : 7
/*
    Kotlin Program for
    Count number of palindromic path in a matrix
*/
class Coordinates
{
	var sc: Int;
	var ec: Int;
	var sr: Int;
	var er: Int;
	constructor(sc: Int, ec: Int, sr: Int, er: Int)
	{
		this.sc = sc;
		this.ec = ec;
		this.sr = sr;
		this.er = er;
	}
}
class PalindromicPath
{
	fun absValue(value: Int): Int
	{
		if (value < 0)
		{
			return -value;
		}
		return value;
	}
	fun countPath(
      matrix: Array < Array < Char >> , 
      dp: HashMap < Coordinates, Int >  , 
      sc : Int, ec: Int, sr: Int, 
      er: Int, n: Int, m: Int): Int
	{
		if (sc < 0 || ec < 0 || sr < 0 || er < 0 ||
            sc >= m || ec >= m || sr >= n || er >= n)
		{
			// When index are out of range
			return 0;
		}
		if (sc > ec || sr > er)
		{
			// Overlapping case
			return 0;
		}
		else if (matrix[er][ec] != matrix[sr][sc])
		{
			// When palindrome not exist in given indexes
			return 0;
		}
		else if (this.absValue((sr - er) + (sc - ec)) <= 1)
		{
			return 1;
		}
		val point: Coordinates = Coordinates(sc, ec, sr, er);
		if (dp.containsKey(point))
		{
			// When point already exists
			return dp.getValue(point);
		}
		// Calculate palindromic path using recursion
		val count: Int = 
          this.countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m) + 
          this.countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m) + 
          this.countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m) + 
          this.countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m);
		dp.put(point, count);
		return count;
	}
	// This function are handling the request of counting palindromic path.
	fun countPalindromicPath(matrix: Array < Array < Char >> ): Unit
	{
		// Get the length
		val n: Int = matrix.count();
		val m: Int = matrix[0].count();
		// Manage coordinates points
		val dp: HashMap < Coordinates, Int > = HashMap < Coordinates, Int > ();
		val result: Int = this.countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m);
		print("\n Result : " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: PalindromicPath = PalindromicPath();
	val matrix: Array < Array < Char >> = arrayOf(
      arrayOf('a', 'a', 'a', 'b'), 
      arrayOf('b', 'b', 'c', 'b'), 
      arrayOf('b', 'b', 'c', 'a'), 
      arrayOf('a', 'a', 'b', 'a'), 
      arrayOf('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  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
	    --------------------------
	    Result = 7
	*/
	task.countPalindromicPath(matrix);
}

Output

 Result : 7

Expected Output:

The given matrix:

a a a b
        b b c b
        b b c a
        a a b a
        a b b a
        

The expected result is 7, indicating that there are seven palindromic paths in the matrix.

Time Complexity:

The time complexity of this solution is dependent on the size of the matrix. Let's assume the matrix has dimensions n x m. Since we are using memoization (storing intermediate results in the hashmap), the recursive calls for the same coordinates will have constant time complexity. Therefore, the overall time complexity of the program is O(n * m).

In this article, we discussed a Java program to count the number of palindromic paths in a matrix. We provided a detailed explanation of the algorithm used, along with the problem statement and expected output. Additionally, we analyzed the time complexity of the code. By implementing this program, we can efficiently determine the count of palindromic paths in any given matrix.

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