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.

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.


Feel free to post your doubts below :)


Popular posts from this blog

Finding the Longest Palindrome in a String

Finding a Single Number amongst Repeated Numbers [Repeated Twice]

Finding the Longest Path From One Point To Another - Dynamic Programming