md.ashif313's blog

Minimum Insertion needed to make a string palindrome
By md.ashif313, history, 7 years ago, In English

I'm trying to find an algorithm for calculating Minimum Insertion needed to make a string palindrome. My Idea is to find the length of longest palindromic sub sequence for the given string and subtract it from the string length. Will it work? Or there is any cornered case where it will not work, Please help !!!!

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Let dp[l][r] be the minimum number of insertions to make s[l...r] a palindrome.

If s[l] = s[r], then obviously dp[l][r] = dp[l + 1][r - 1].

Otherwise, you must either add s[r] to the beginning or s[l] to the end so dp[l][r] = 1 + min(dp[l + 1][r], dp[l][r - 1]).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi Petar, Thank you very much for your Idea. That's really good. :)

    But can you please tell me if there is any pitfall for my approach, thank you in advance :)

    → Reply