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
- 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). - We create a class named "PalindromicPath" that contains the main logic for counting the palindromic paths.
- Inside the "PalindromicPath" class, we define a method called
absValueto calculate the absolute value of a number. - We create a method named
countPaththat takes the matrix, a hashmap to store intermediate results (dp), and the starting and ending coordinates of a path. - 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.
- If the characters at the start and end coordinates are not the same, we return 0 as well since a palindrome cannot be formed.
- 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.
- Next, we create an instance of the "Coordinates" class with the provided coordinates.
- We check if the hashmap already contains the current coordinates. If it does, we retrieve the count and return it.
- 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)
- Moving down and up:
- We add up the counts obtained from these recursive calls.
- Finally, we store the count in the hashmap and return it.
- In the main function, we create an instance of the "PalindromicPath" class.
- We define a sample matrix and pass it to the
countPalindromicPathmethod. - 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 : 7package 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 : 7import 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 : 7Expected 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 dimensionsn 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.
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