[POJ]1159 Palindrome

A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.

As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome. 

题意是要求最少插入多少个字符，可以让输入串变成回文。标准的DP问题，如果我们用dp[i][j]表示最少插入的字符数可以让子串s[i:j]变成回文，我们可以求得递推公式：

• dp[i][j] = dp[i + 1][j - 1], if s[i] == s[j]
• dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1

空间复杂度和时间复杂度都为O(n^2)，n为输入子串的长度。代码如下：

另一种做法，对于给定输入的字符串s，如果其最长的回文子序列为p，那么其剩余没有对应字符能形成回文的字符的数量为len(s) - len(p)。我们只要针对这些字符，加上对应的字符使他们在新的字符串s'当中有对称的字符，这就是我们最少要额外加上的字符。比如对于字符串"adbcdxbd"当中，我们能找到的最长回文子序列为"dbcbd"，那么剩下的字符我们插入对应的对称字符，我们可以得到"adb(xd)cdxbd(a)"。括号内为新插入的字符。至于为什么这个一定是插入最少的，因为我们找的是最长的回文子序列。剩下的那些字符，无论如何我们都是要插入字符和其match的。所以这道题其实就等价于找最长回文子序列，参考这篇文章。时间复杂度O(n^2)，空间复杂度可以用滚动数组优化到O(n)，代码如下：