0

我需要找到将字符串转换为回文所需的最少插入次数。注意：插入可以发生在任何地方、末尾或内部。如果只是在最后，我们这里有个问题。

所以我发现这可以O(N**2)通过这个简单的技巧及时完成：

  1. 设字符串为 s1。扭转它。让它成为s2。说长度是l。
  2. 现在找到 s1 和 s2 的最长公共子序列。让它的长度为x。
  3. 答案是l-x。

例如，假设s1 = abcda. 因此s2 = adcba。长度是 5。最长的公共子序列aba的长度是 3。所以插入的最小数量是5-3 = 2，这是实际的答案，结果是字符串 - 。adcbcda

但是，我无法理解其背后的逻辑。谁能向我解释它为什么有效？

而且，有没有O(N)可能的解决方案？

4

1 回答 1

1

我不知道是否有O(N)解决方案，但是通过与相反的比较，您会发现一个子序列是回文。然后你有l-x不成对的字母。（如果你在单词的中间有一面镜子，你可以将一个字母的对视为它的反射。例如 ab|ba） 稍后，通过插入，你就完成了图片。

现在，首先，我们如何找到两个字符串共有的（最大）子序列？有一个多项式算法可以在这里找到它 https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

当我们试图找到 s1 和 s2（s1 的反向）之间的最长公共子序列（lcs）时，我们实际上在 s1 的前半部分和 s2 的前半部分之间找到了 lcs，同时也在 s1 的后半部分和 s2 的后半部分之间找到了 lcs。认为

s1 =abcddzac

所以 s2 = cazddcba. 在这里，我们可以将其视为abcd与cazd（前半部分）的比较加上dzac与dcba（后半部分）的比较。我们可以看到两个比较是相同的，只是它们是相反的，所以它们的连接必须是回文，所以 s1 和 s2 的 lcs 必须是回文。

一旦我们有了长度为 4 的 lcs( ad|da)，我们还有 4 个破坏对称性的字母 (b,c,z,c)。然后我们为它们中的每一个插入一个字母以形成对称，即回文。我们将中点设置为 lcs 的中点，并考虑将 s1 从该中点分成两部分，因此我们有

s1 = abc d|dz ac 我们把它像一根棍子一样从 d|d 分成两半，我们最终得到：
dz ac
dcba

现在我们只需在 lcs 的字母之间填充，使它们相同。在我们的案例中，步骤如下：

dz ac
dcb a

dz ac
dzcb a

dzc ac
dzcb a

dzcb ac
dzcb a

dzcb ac
dzcb ac


现在我们从同一点解开它，我们有
c abcz ddzcb ac 这是一个回文。

注意：cddc 也是一个 ldc，但这不会改变步数。

于 2016-04-27T16:07:18.463 回答