插入字符串以将其转换为回文的最小字符数
我需要找到将字符串转换为回文所需的最少插入数。注意:插入可以发生在任何地方，在最后，或在内部。如果它只是在最后，我们有一个问题here。
因此，我发现这可以通过这个简单的技巧在O(N**2)时间完成：
- 将字符串设为s1。倒过来。让它成为s2。假设长度是
l。 - 现在找出s1和s2最长的公共子序列。让它的长度是
x。 - 答案是
l-x。
例如，假设s1 = abcda。因此，s2 = adcba.长度为5。最长的公共子序列是长度为3的aba。因此插入的最小数目是5-3 = 2，这是实际的答案，其结果是字符串-5-3 = 2。
不过，我不明白背后的逻辑。有人能给我解释一下为什么会起作用吗？
还有，有什么O(N)解决方案可以解决这个问题吗？
回答 1
Stack Overflow用户
发布于 2016-04-27 16:07:18
我不知道是否有O(N)解决方案，但通过与反向比较，您可以找到一个子序列，即回文。然后你有不成对的l-x字母。(如果你在单词的中间有一面镜子，你可以把一封信的对子当作它的反射。稍后，通过插入，您只需完成图片。
首先，我们如何找到两个字符串共有的(最大)子序列？有一种多项式算法可以在这里找到它，problem
当我们试图寻找s1和s2 (反向s1)之间最长的公共子序列( lcs )时，实际上是在s1的前半部分和s2的前半部分，也就是s1的下半部分和s2的下半部分之间。假设
s1 = abcddzac
所以s2 = cazddcba。这里我们可以把它看作是abcd和cazd(上半部分)的比较，再加上dzac和dcba(下半部分)的比较。我们可以看到，这两种比较是相同的，除了它们是相反的，所以它们的连接必须是回文，所以s1和s2的lcs必须是回文。
一旦我们得到长度为4的lcs(ad|da)，我们又有4个破坏对称性的字母(b，c，z，c)。然后，我们为每个字母插入一个字母，使其具有对称性，即回文。我们将中间点设为lcs的中间点，并考虑将s1从中间点分解为两个，所以我们有
s1 = a bc d|d z a c，我们把它像一根棍子一样从d\\d分解成两个，最后得到：
dzac
dcba
现在，我们简单地在lcs的字母之间填充，使它们是相同的。在我们的例子中，步骤如下：
dzac
dcba
dzac
dzcba
dzcac
dzcba
dzcbac
dzcba
dzcbac
dzcbac
现在我们把它从同样的点上解开，我们已经
cabczddzcbac是回文。
注意: cddc也是最不发达国家，但这不会改变步骤的数量。
https://stackoverflow.com/questions/36893663
复制相似问题
腾讯云开发者
