如何将字符串转换为回文，删除字符串的字符数最少

Question

假设字符串是"anuja"，输出应该是2，因为如果我去掉字符"u"one_answers"n"，给定的字符串就会变成回文。因此，产出应该是清除的最小数量。更多示例：输入字符串："ababa"输出：0(不需要删除(输入字符串："abcdba"输出：1(删除"c"或"d"(请解释一下算法。

Answer 1

设dp[i, j] = minimum number of removals needed to convert the substring [i, j] to a palindrome。我们有：

dp[i, i] = 0 for all i (every single character is a palindrome)

要查找dp[i, j]，让我们考虑一个随机字符串。我们有两种可能性：

1. 第一个和最后一个字符相等：a[i] == a[j]。在这种情况下，我们可以将问题简化为找到需要删除的最小字符数，以使子字符串[i+1, j-1]成为回文。

2. 第一个和最后一个字符不相等：a[i] != a[j]。在这种情况下，我们需要删除其中一个。我们将消除这一点，从而找到更好的解决方案。

所以我们有：

dp[i, j] = dp[i + 1, j - 1]                     # if a[i] == a[j]
           min(dp[i + 1, j], dp[i, j - 1]) + 1  # otherwise

以anuja为例。我们会得到：

  | 1 2 3 4 5
-------------
1 | 0 1 2 2 2
2 |   0 1 2 3
3 |     0 1 2
4 |       0 1
5 |         0          

注意，矩阵是从主对角线开始计算的，并按顺序向上连续，对角线平行于主对角线。答案是dp[1, n]。

这类似于Levenstein距离，但它只考虑移除。

Answer 2

您可以测量从字符串到其反面的编辑距离(levenstein距离((忽略替换(。所需的值将是该值的一半。

这个问题类似于UVA 10739。下面是一个示例实现。

示例实现(适用于您的情况(可以是：

string P, Q;
getline(cin, P);
Q = string(P.rbegin(), P.rend());
int p = P.size(), q = Q.size();
for(int i=0; i<=p; i++) { T[i][0] = i; }
for(int i=0; i<=q; i++) { T[0][i] = i; }
for(int i=1; i<=p; i++) {
    for(int j=1; j<=q; j++) {
        if (P[i-1] == Q[j-1])
            T[i][j] = T[i-1][j-1];
        else
            T[i][j] = min(T[i-1][j], T[i][j-1]) + 1;
    }
}
cout << "Case " << tt << ": " << T[p][q]/2 << endl;