用最少的插入将字符串转换为回文字符串

Question

为了找到将给定字符串转换为回文所需的最小插入次数，我找到了字符串的最长公共子序列(Lcs_string)及其反转。因此，插入的次数是length(s) - length(lcs_string)

在知道要插入的次数的情况下，应该采用什么方法来找到等效的回文字符串？

例如：

1) azbzczdzez

需要插入的次数:5回文字符串: azbzcezdzeczbza

虽然同一字符串可能存在多个回文字符串，但我只想找到一个回文字符串？

Answer 1

假设S[i, j]表示字符串S的子字符串，从索引i开始，到索引j (包括索引j)结束，c[i, j]是S[i, j]的最佳解决方案。

显然，c[i, j] = 0 if i >= j。

一般来说，我们有递归：

​

​

Answer 2

为了详细说明VenomFangs answer，有一个简单的动态编程解决方案。注意，我假设这里唯一允许的操作是插入字符(不删除，不更新)。设S是n个字符的字符串。用于此的简单递归函数P为：

    = P [i+1 .. j-1], if S[i] = S[j] 

Pi..j

    = min (P[i..j-1], P[i+1..j]) + 1,

如果你想了解更多关于这是真的原因的解释，请发表评论，我很乐意解释(尽管这很容易理解)。顺便说一句，这与您使用的LCS函数完全相反，从而验证了您的解决方案实际上是最优的。当然，我完全有可能搞砸了，如果是这样的话，有人一定要让我知道！

编辑:为了说明回文字符串本身，这可以很容易地完成，如下所示：如上所述，P1..n将给出使该字符串成为回文字符串所需的插入次数。一旦构建了上面的二维数组，下面就是如何找到回文数组：

从i=1，j=n开始。现在，字符串输出= ""；

while(i < j)
{
    if (P[i][j] == P[i+1][j-1]) //this happens if no insertions were made at this point
    {
        output = output + S[i];
        i++;
        j--;
    }
    else
    if (P[i][j] == P[i+1][j]) //
    {
        output = output + S[i];
        i++;
    }
    else
    {
        output = S[j] + output;
        j--;
    }
 }
 cout<<output<<reverse(output);
 //You may have to be careful about odd sized palindromes here,
 // I haven't accounted for that, it just needs one simple check

这会使阅读效果变得更好吗？

Answer 3

这个解决方案看起来是一个动态编程解决方案。

你可以在下面的帖子中找到答案：How can I compute the number of characters required to turn a string into a palindrome?