0

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

Community
  • 1
  • 1
User_Targaryen
  • 4,125
  • 4
  • 30
  • 51
  • 2
    Possible duplicate of http://stackoverflow.com/questions/19801081/find-all-substrings-that-are-palindromes – Codor Sep 28 '16 at 12:01
  • If you define substring as substring(start, end) instead of substring(start, length) then half of your matrix will be zero since it's invalid values (end < start) – samgak Sep 28 '16 at 12:03
  • @samgak: I know that!!! The diagonally upper right half of the matrix is going to be 0 always – User_Targaryen Sep 28 '16 at 13:04
  • You need to check all the length 2 substrings too, and from there you can use your rule to produce the rest. – biziclop Sep 28 '16 at 13:04

1 Answers1

2

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
Yanhui Zhou
  • 872
  • 6
  • 20