如何将一个字符串转换为回文字符串，并且最小化删除字符串中的字符数量？

Question

如何将一个字符串转换为回文字符串，并且最小化删除字符串中的字符数量？

3

假设字符串为“anuja”，输出应该是2，因为如果我删除字符'u'和'n'，给定的字符串就变成了回文。因此，输出应该是最小的删除次数。更多例子：输入字符串："ababa" 输出：0（不需要删除）输入字符串："abcdba" 输出：1（删除'c'或'd'）请解释算法。

- Kryptics

1

不错的问题。你已经尝试了什么？你的解决方案有什么问题？ - user4668606

2个回答

1

你可以测量字符串到其反转字符串的编辑距离（Levenshtein距离）（忽略替换）。所需值将是此值的一半。

该问题类似于 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;

- Juan Lopes

在你提供的问题中，你可以添加、删除和替换字符。但是在这里，你只能删除它们。为什么这两个问题是相同的？ - IVlad

@IVlad 你说得对，虽然从不同的角度来看，添加和删除是相同的操作。那么只需要从递归中删除T[i-1][j-1]即可，但你在你的答案中已经做到了这一点。我会保留这个答案，因为我认为计算字符串和其反转之间的编辑距离的原理很有用 :) - Juan Lopes

@Juan Lopes..谢谢你的回答..很有帮助。 - Kryptics

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted Answer

令 dp[i, j] = 将子串 [i, j] 转换为回文所需的最小删除次数。我们有:

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] 。

这类似于 Levenshtein距离，不过它只考虑了删除操作。