要插入字符串以将其转换为回文的最少字符数
Minimum number of characters to be inserted in a string to convert it to palindrome
我需要找到将字符串转换为回文所需的最少插入次数。注意：插入可以发生在任何地方，末尾或内部。如果只是在最后，我们有一个问题。
所以我发现可以通过这个简单的技巧在 O(N**2) 时间内完成：
- 设字符串为s1。反转它。让它成为s2。假设长度是
l.
- 现在求s1和s2的最长公共子序列。设其长度为
x.
- 答案是
l-x。
例如，假设s1 = abcda。因此s2 = adcba。长度为 5。最长公共子序列是长度为 3 的 aba。因此最小插入数是 5-3 = 2，这是实际答案，结果字符串 - adcbcda.
但是，我无法理解其背后的逻辑。谁能向我解释为什么它有效？
而且，是否有任何 O(N) 可能的解决方案？
我不知道有没有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 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 也是一个 ldc，但不会改变步数。
我需要找到将字符串转换为回文所需的最少插入次数。注意：插入可以发生在任何地方，末尾或内部。如果只是在最后，我们有一个问题
所以我发现可以通过这个简单的技巧在 O(N**2) 时间内完成：
- 设字符串为s1。反转它。让它成为s2。假设长度是
l. - 现在求s1和s2的最长公共子序列。设其长度为
x. - 答案是
l-x。
例如，假设s1 = abcda。因此s2 = adcba。长度为 5。最长公共子序列是长度为 3 的 aba。因此最小插入数是 5-3 = 2，这是实际答案，结果字符串 - adcbcda.
但是，我无法理解其背后的逻辑。谁能向我解释为什么它有效？
而且，是否有任何 O(N) 可能的解决方案？
我不知道有没有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 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 也是一个 ldc，但不会改变步数。