# Number of palindromic paths in a matrix  Difficulty Level Hard
Dynamic Programming Matrix Palindrome

## Problem Statement  We are given a two-dimensional matrix containing lowercase English alphabets, we need to count the number of palindromic paths in it. A palindromic path is nothing but a path following palindromic property. A word which when reversed remains the same as the initial word is said to be a palindrome. We need to count the number of paths from the initial point to the destination. Our starting point is the top-left cell and the destination is the bottom right corner. There is also a condition imposed on the direction of movement. We move in the right and bottom direction from the current cell.

## Example   ```Matrix = { a a b

a z a

b a a }
```
`6`

Explanation: There are 6 ways to get a palindromic path from a given matrix. Because we can move from an initial point (0,0) to (0,1) and (1,0) only.

The four paths are aabaa, aazaa, aazaa, aabaa, aazaa, aazaa. The two of the paths are similar. Because the given matrix is symmetric about principal diagonal. That is the reason because we have two similar palindromic paths.

`{a}`
`1`

Explanation: Since there is only a single path “a” which is also a palindrome. The answer is 1.

## Approach for number of palindromic paths in a matrix problem  ### Naive Approach

In this problem, we will use recursion to find all the possible sequences of paths and then check if the path is palindrome or not. The approach told before used backtracking which is not efficient enough. Since backtracking generates all possible solutions. We check all of these solutions if they are palindrome. Since this is not efficient enough we keep two variables for alphabets in the path from initial point and destination.

Convert Sorted List to Binary Search Tree

### Efficient Approach

Now, we can summarise our algorithm. We use two variables which store the cells, one from starting and one from the end. These two stored variables should be the same for satisfying palindromic property. We move ahead if the alphabets are the same. By moving ahead, I meant we make a recursive call for subproblem in all possible directions. Whenever we have a recursive solution. We can think of dynamic programming if there are overlapping subproblems. Since we will be solving some subproblems multiple times, it is better if we store their results. We can use a map for storing the result of the subproblem. Indices of starting and ending cells serve as a key for the map. This is how we find  number of palindromic paths in a 2D array

## Code for number of palindromic paths in a matrix problem  ### C++ Code

```#include <bits/stdc++.h>
using namespace std;

// checks if index i,j is valid or not (lies inside matrix or not)
bool isValid (int n, int m, int i, int j) {
return !(i < 0 || i >= n || j < 0 || j >= m);
}

// return number of palindromic paths in matrix
int solvePalindromicPaths(vector<vector<char>> &matrix, int startRow, int startCol, int endRow, int endCol, map<pair<pair<int,int>,pair<int,int>>,int> &dp) {
int n = matrix.size(), m = matrix.size();

// check if start and end cell indices are valid (are inside matrix)
if (!isValid(n, m, startRow, startCol) || !isValid(n, m, endRow, endCol))
return 0;
// if start indices are after end indices, they can not meet in middle
if (startRow > endRow || startCol > endCol)
return 0;
// if path does not follow palindromic property
if (matrix[startRow][startCol] != matrix[endRow][endCol])
return 0;
// indices are adjacent to each other
if (abs((startRow - endRow) + (startCol - endCol)) <= 1)
return 1;
// store indices as pair, since our map is using indices as key
pair<pair<int,int>,pair<int,int>> indices = pair<pair<int,int>,pair<int,int>>
(pair<int,int>(startRow, startCol), pair<int,int>(endRow, endCol));

// if sub-problem has alredy been calculated
if(dp.count(indices))
return dp[indices];

// if not calculated, calculate result by recursively calling in all directions
int countOfPalindromicPaths = 0;
countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow + 1, startCol, endRow - 1, endCol, dp);
countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow + 1, startCol, endRow, endCol - 1, dp);
countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow, startCol + 1, endRow - 1, endCol, dp);
countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow, startCol + 1, endRow, endCol - 1, dp);

// store and return the result
return dp[indices] = countOfPalindromicPaths;
}

int main() {
int t;cin>>t;
while(t--){
int n,m;cin>>n>>m;
vector<vector<char>> matrix(n, vector<char>(m));
map<pair<pair<int,int>,pair<int,int>>,int> dp;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
cin>>matrix[i][j];
}
cout<<solvePalindromicPaths(matrix, 0, 0, n-1, m-1, dp)<<endl;
}
}
```
```2
2 2
a b
b a
3 3
a a b
a z a
b a a
```
```2
6```

### Java Code

```import java.util.*;
import java.lang.*;
import java.io.*;

class Indices {
private int startRow;
private int startCol;
private int endRow;
private int endCol;

public Indices(int startRow, int startCol, int endRow, int endCol) {
this.startRow = startRow;
this.startCol = startCol;
this.endRow = endRow;
this.endCol = endCol;
}
}

public class Main {

// checks if index i,j is valid or not (lies inside matrix or not)
static boolean isValid (int n, int m, int i, int j) {
return !(i < 0 || i >= n || j < 0 || j >= m);
}

// return number of palindromic paths in matrix
static int solvePalindromicPaths(char[][] matrix, int startRow, int startCol, int endRow, int endCol, int n, int m, HashMap<Indices, Integer> dp) {
// check if start and end cell indices are valid (are inside matrix)
if (!isValid(n, m, startRow, startCol) || !isValid(n, m, endRow, endCol))
return 0;
// if start indices are after end indices, they can not meet in middle
if (startRow > endRow || startCol > endCol)
return 0;
// if path does not follow palindromic property
if (matrix[startRow][startCol] != matrix[endRow][endCol])
return 0;
// indices are adjacent to each other
if (Math.abs((startRow - endRow) + (startCol - endCol)) <= 1)
return 1;
// create an instance of indices with current values, since our map is using indices as key
Indices indices = new Indices(startRow, startCol, endRow, endCol);

// if sub-problem has alredy been calculated
if(dp.containsKey(indices))
return dp.get(indices);

// if not calculated, calculate result by recursively calling in all directions
int countOfPalindromicPaths = 0;
countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow + 1, startCol, endRow - 1, endCol, n, m, dp);
countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow + 1, startCol, endRow, endCol - 1, n, m, dp);
countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow, startCol + 1, endRow - 1, endCol, n, m, dp);
countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow, startCol + 1, endRow, endCol - 1, n, m, dp);

// store and return the result
dp.put(indices, countOfPalindromicPaths);
return countOfPalindromicPaths;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0){
int n = sc.nextInt();
int m = sc.nextInt();
char matrix[][] = new char[n][m];

HashMap<Indices, Integer> dp = new HashMap<>();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++) {
matrix[i][j] = sc.next().charAt(0);
}
}
System.out.println(solvePalindromicPaths(matrix, 0, 0, n-1, m-1, n, m, dp));
}
}
}
```
```2
2 2
a b
b a
3 3
a a b
a z a
b a a```
```2
6```

## Complexity Analysis  ### Time Complexity: O(N*M)

Since we are storing the result of subproblems. Because there is a total of N*M states. We have Time Complexity of O(N*M), which means number of palindromic paths in a matrix problem has polynomial time complexity.