by froghramar » Wed Nov 16, 2016 3:20 pm
If you have already solved some problems based on dynamic programming, you should not find it hard to solve this problem.
Can you write a recursive function to check if a sub-string of a string is palindrome or not? I hope you can. My solution is very similar to a recursive palindrome checker. What do you do in a palindrome checker? If you find a match in both sides of your sub-string S[l, r] you can reduce your problem to S[l + 1, r - 1]. Otherwise, you can say that the sub-string is not palindrome.
Now, you are not asked to answer if the given string is palindrome or not.
Let's define dp[l][r] as the minimum number of characters to add to make the sub-string S[l, r] a palindrome. Now you can solve your problem with two simple transactions.
1. If S[l] and S[r] are equal, you can not get a better solution than considering S[l] and S[r] as reflexive characters of your new palindromic string, as you are not having any cost of adding a new character.
Example, Result("ahbfhba") = Result("hbfhb");
So, dp[l][r] = dp[l + 1][r - 1], if S[l] = S[r].
2. If S[l] and S[r] are not equal, then you have no other option than adding an extra character in one of the sides to have a match. Let say, your current string is dfghdc. If you want to have a match in both sides, you can make it dfghdcd or cdfghdc.
Result("dfghdc") = 1 + Minimum ( Result("fghdc"), Result("dfghd") ).
So, dp[l][r] = 1 + Minimum (dp[l + 1][r], dp[l][r - 1]), if S[l] != S[r].