Given a matrix containing lower alphabetical characters only of size n*m. We need to count the number of palindromic paths in the given matrix.
A path is defined as a sequence of cells starting from top-left cell and ending at bottom-right cell. We are allowed to move to right and down only from current cell.
 
Example 1:
Input: matrix = {{a,a,a,b},{b,a,a,a},{a,b,b,a}}
Output: 3
Explanation: Number of palindromic paths are 3 
from top-left to bottom-right.
aaaaaa (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> 
(1, 3) -> (2, 3)    
aaaaaa (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> 
(1, 3) -> (2, 3)    
abaaba (0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> 
(2, 2) -> (2, 3)
Example 2:
Input: matrix = {{a,b},{c,d}}
Output: 0
Explanation: There is no palindromic paths.
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function countPalindromicPaths() which takes the matrix as input parameter and returns the total nuumber of palindromic paths modulo 10^{9} + 7.
 
Expected Time Complexity: O(n^{2}*m^{2})
Space Complexity: O(n*m)
 
Constraints:
1 ≤ n, m ≤ 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

String algorithms

Starter code: #User function Template for python3

class Solution:
	def countOfPalindromicPaths(self, matrix):
		# Code here

Solutions:
class Solution:

	def solve(self, ma, i1, j1, i2, j2, dp):
		n = len(ma)
		m = len(ma[0])
		if i1 >= n or j1 >= m or i2 < 0 or (j2 < 0) or (i1 > i2) or (j1 > j2) or (ma[i1][j1] != ma[i2][j2]):
			return 0
		if i1 == i2 and j1 == j2 or (i1 == i2 and j1 + 1 == j2) or (j1 == j2 and i1 + 1 == i2):
			return 1
		x = i1 * n + j1
		y = i2 * n + j2
		if x in dp and y in dp[x]:
			return dp[x][y]
		ans = 0
		ans = (ans + self.solve(ma, i1 + 1, j1, i2 - 1, j2, dp)) % self.M
		ans = (ans + self.solve(ma, i1 + 1, j1, i2, j2 - 1, dp)) % self.M
		ans = (ans + self.solve(ma, i1, j1 + 1, i2 - 1, j2, dp)) % self.M
		ans = (ans + self.solve(ma, i1, j1 + 1, i2, j2 - 1, dp)) % self.M
		if not x in dp:
			dp[x] = {}
		if not y in dp[x]:
			dp[x][y] = ans
		return ans

	def countOfPalindromicPaths(self, matrix):
		dp = {}
		n = len(matrix)
		for i in range(n):
			if matrix[i][-1] == ' ':
				matrix[i].pop()
		m = len(matrix[0])
		self.M = int(1000000000.0 + 7)
		return self.solve(matrix, 0, 0, n - 1, m - 1, dp)


class Solution:

	def countOfPalindromicPaths(self, matrix):
		mp = {}
		M = 1000000007

		def findP(arr, i, j, p, q, n, m):
			n = len(arr)
			m = len(arr[0])
			if i >= n or j >= m or p < 0 or (q < 0):
				return 0
			if arr[i][j] != arr[p][q]:
				return 0
			if i == p and j == q or (abs(i - p) == 1 and j - q == 0) or (i - p == 0 and abs(j - q) == 1):
				return 1
			if i > p or j > q:
				return 0
			curr = str(i) + '&' + str(j) + '&' + str(p) + '&' + str(q)
			if curr in mp:
				return mp[curr]
			op1 = findP(arr, i, j + 1, p, q - 1, n, m)
			op2 = findP(arr, i, j + 1, p - 1, q, n, m)
			op3 = findP(arr, i + 1, j, p, q - 1, n, m)
			op4 = findP(arr, i + 1, j, p - 1, q, n, m)
			mp[curr] = (op1 + op2 + op3 + op4) % M
			return mp[curr]
		n = len(matrix)
		m = len(matrix[-1])
		return findP(matrix, 0, 0, n - 1, m - 1, n, m) % M


class Solution:

	def __init__(self):
		self.mod = 10 ** 9 + 7
		self.dp = {}

	def countOfPalindromicPaths(self, matrix):
		return self.path(matrix, 0, 0, len(matrix) - 1, len(matrix[0]) - 1) % self.mod

	def path(self, matrix, i, j, x, y):
		if i >= len(matrix) or j >= len(matrix[0]) or x < 0 or (y < 0) or (matrix[i][j] != matrix[x][y]):
			return 0
		if i == x and j == y or abs(i - x) + abs(j - y) <= 1:
			return 1
		if i > x or j > y:
			return 0
		if (i, j, x, y) in self.dp:
			return self.dp[i, j, x, y]
		op1 = self.path(matrix, i + 1, j, x - 1, y) % self.mod
		op2 = self.path(matrix, i + 1, j, x, y - 1) % self.mod
		op3 = self.path(matrix, i, j + 1, x - 1, y) % self.mod
		op4 = self.path(matrix, i, j + 1, x, y - 1) % self.mod
		temp = (op1 + op2 + op3 + op4) % self.mod
		self.dp[i, j, x, y] = temp
		return temp


class Solution:

	def countOfPalindromicPaths(self, matrix):
		m = len(matrix)
		n = len(matrix[0])
		memo = {}
		count = self.helper(matrix, 0, 0, m - 1, n - 1, m, n, memo)
		return count

	def helper(self, matrix, t_i, t_j, d_i, d_j, m, n, memo):
		if t_i < 0 or t_i > m - 1 or t_j < 0 or (t_j > n - 1):
			return 0
		if d_i < 0 or d_i > m - 1 or d_j < 0 or (d_j > n - 1):
			return 0
		if t_i > d_i or t_j > d_j:
			return 0
		if (t_i, t_j, d_i, d_j) in memo:
			return memo[t_i, t_j, d_i, d_j]
		if matrix[t_i][t_j] != matrix[d_i][d_j]:
			return 0
		if t_i == d_i and t_j == d_j or (t_i + 1 == d_i and t_j == d_j) or (t_i == d_i and t_j + 1 == d_j):
			return 1
		count = 0
		count += self.helper(matrix, t_i, t_j + 1, d_i - 1, d_j, m, n, memo)
		count += self.helper(matrix, t_i, t_j + 1, d_i, d_j - 1, m, n, memo)
		count += self.helper(matrix, t_i + 1, t_j, d_i - 1, d_j, m, n, memo)
		count += self.helper(matrix, t_i + 1, t_j, d_i, d_j - 1, m, n, memo)
		count = count % (10 ** 9 + 7)
		memo[t_i, t_j, d_i, d_j] = count
		return memo[t_i, t_j, d_i, d_j]


class Solution:

	def countOfPalindromicPaths(self, arr):
		n = len(arr)
		m = len(arr[0])
		memo = {}

		def pali(s, e):
			global count
			(x1, y1) = s
			(x2, y2) = e
			if x1 > x2 or y1 > y2:
				return 0
			if x1 == x2 and y1 == y2:
				return 1
			elif x2 == x1 + 1 and y1 == y2 or (x1 == x2 and y2 == y1 + 1):
				return 1
			if (x1, x2, y1, y2) in memo:
				return memo[x1, x2, y1, y2]
			a1 = 0
			a2 = 0
			a3 = 0
			a4 = 0
			if (x1 <= x2 - 1 and y1 + 1 <= y2) and arr[x1][y1 + 1] == arr[x2 - 1][y2]:
				a1 = pali([x1, y1 + 1], [x2 - 1, y2])
			if (x1 <= x2 and y1 + 1 <= y2 - 1) and arr[x1][y1 + 1] == arr[x2][y2 - 1]:
				a2 = pali([x1, y1 + 1], [x2, y2 - 1])
			if (x1 + 1 <= x2 and y1 <= y2 - 1) and arr[x1 + 1][y1] == arr[x2][y2 - 1]:
				a3 = pali([x1 + 1, y1], [x2, y2 - 1])
			if (x1 + 1 <= x2 - 1 and y1 <= y2) and arr[x1 + 1][y1] == arr[x2 - 1][y2]:
				a4 = pali([x1 + 1, y1], [x2 - 1, y2])
			memo[x1, x2, y1, y2] = a1 + a2 + a3 + a4
			return memo[x1, x2, y1, y2]
		count = 0
		if arr[0][0] == arr[n - 1][m - 1]:
			count = pali([0, 0], [n - 1, m - 1])
		return count % (10 ** 9 + 7)