md.ashif313's blog

By md.ashif313, history, 5 weeks 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  

»
5 weeks 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]).

  • »
    »
    5 weeks 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 :)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't know, perhaps you can try submitting it on SPOJ (http://www.spoj.com/problems/IOIPALIN/). If it doesn't get accepted, then implementing my approach and stresstesting it against yours should easily produce a counter-example