CODEWITHSUNDEEP
algorithmmatrixdynamic-programming
User_Targaryen
User_Targaryen

Reputation: 4225

Dynamic Programming to find all palindromic substrings

I was trying to solve a question via dynamic programming. I have a string and I need to find all the possible palindromic substrings. Say, I have a string of length n. I have created a matrix n*n for the lookup. A cell (i,j) is either 1 or 0. If it is 1, it means that the substring[i..j] is a palindrome, otherwise 0. Initially the diagonals are 1 because every character itself is a palindrome.

I need to fill the matrix properly as stated above.

I figured out the following:

  1. If substring[i..j] is a plaindrome, then I can find if substring[i-1..j+1] is palindrome in O(1) time by checking if matrix[i][j]==1 and word[i-1] == word[j+1]..

How can I go about filling the matrix, for other general cases.

A small explanation with pseudocode/language specific implementation to fill out the matrix will be much appreciated

Initial Matrix

Edit: I need some explanation as to how and in which order the matrix gets filled (i.e diagonally, horizontally etc) . I want to solve the question by filling out this matrix only, and by no other method. My question is not a duplicate of this

Upvotes: 0

Views: 1949

Answers (1)

Yanhui Zhou
Yanhui Zhou

Reputation: 898

The palindromic substrings can be checked from whose length is one to N. 

  For i from 1 to n
       Mark all substring of length i is palindromic or not.

pseudocode: (string array 1-based)

for len=1 to n:  // check string from length 1 to n
    for i=1 to (n-len + 1):  // substring start from 1 to （n-len+1)
        j = i + len - 1
        if len == 1:
           matrix[i][j]==1 
        else if len == 2:
           if array[i] == array[j]:
               matrix[i][j] = 1
           else:
               matrix[i][j] = 0
        else:
           if matrix[i+1][j-1] == 1 and array[i] == array[j]:
               matrix[i][j] = 1
           else:
               matrix[i][j] = 0

Upvotes: 2

Related Questions