### Printing All Palindromic Strings in a Matrix

We are given a character matrix and we need to find the list of all the palindromic strings in that matrix starting from the top left corner to the bottom right corner i.e the first character of all the strings must be the top left character in the matrix and the last character must be the bottom right character. The other important condition is that you can only move either towards the right or towards the bottom while tracing a string in the matrix.

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)

We can follow a backtrack approach to solve this problem. According to Wikipedia backtracking is defined as :

We initially start from the top left corner of the matrix (with i = 0, denoting the rows and j = 0, denoting the columns). We check if the current string is a palindrome if i = number of rows and j = number of columns. If not then we call the function twice recursively incrementing i in one call and j in the other.

Feel free to post your doubts below :)

**Sample Input****Input Matrix is given below**

*a a a b**b a a a**a b b a***Sample Output****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)

**Solution Approach**We can follow a backtrack approach to solve this problem. According to Wikipedia backtracking is defined as :

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.

We initially start from the top left corner of the matrix (with i = 0, denoting the rows and j = 0, denoting the columns). We check if the current string is a palindrome if i = number of rows and j = number of columns. If not then we call the function twice recursively incrementing i in one call and j in the other.

**Code**

Feel free to post your doubts below :)

## Comments

## Post a Comment