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 !!!!
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 152 |
| 3 | Proof_by_QED | 146 |
| 3 | Um_nik | 146 |
| 5 | Dominater069 | 144 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
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]).
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 :)
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
Thank You :)
Accepted... :D I think my Idea is OK...
Thank you very much for that nice problem ....
bro just take the string and rev_s string any try to find length longest common subsequence(this will give you the length of longest palindromic subsequence), yea now you have your ans as (s.size() — lcs).