<分区>
这是一个非常有趣的面试问题:
Given a word, append the fewest number of letters to it to convert it into a palindrome.
例如，如果给定的字符串是“hello”，则结果应该是“helloleh”。如果给出“coco”，结果应该是“cococ”。
我能想到的一种方法是将字符串的反向追加到原始字符串的末尾，然后尝试从末尾消除多余的字符。但是，我不知道如何有效地做到这一点。有人有什么想法吗？
<分区>
这是一个非常有趣的面试问题:
Given a word, append the fewest number of letters to it to convert it into a palindrome.
例如，如果给定的字符串是“hello”，则结果应该是“helloleh”。如果给出“coco”，结果应该是“cococ”。
我能想到的一种方法是将字符串的反向追加到原始字符串的末尾，然后尝试从末尾消除多余的字符。但是，我不知道如何有效地做到这一点。有人有什么想法吗？
最佳答案
好的!这是我的第二次尝试。
我们的想法是，在追加额外字符以完成回文时，我们想找出字符串末尾有多少字符可以重复使用。为此，我们将使用 KMP 字符串匹配算法的修改版。使用 KMP，我们搜索原始字符串的反向。一旦我们到达字符串的末尾，我们将在字符串的反转和出现在字符串末尾的原始字符串之间尽可能多地匹配。例如:
HELLO
O
1010
010
3202
202
1001
1001
此时，除非原始字符串是回文，否则 KMP 通常会说“不匹配”。然而，由于我们目前知道有多少字符串的反向匹配，我们可以改为只计算出还有多少字符仍然缺失，然后将它们附加到字符串的末尾。在第一种情况下，我们缺少 LLEH。在第二种情况下，我们缺少 1。在第三个中，我们缺少 3。在最后一种情况下，我们没有遗漏任何东西，因为初始字符串是回文。
该算法的运行时间是标准 KMP 搜索的运行时间加上反转字符串所需的时间:O(n) + O(n) = O(n)。
所以现在要争论正确性。这需要一些努力。考虑最佳答案:
| original string | | extra characters |
假设我们从末尾倒着读，这意味着我们至少要从原字符串的反面读。这个反转字符串的一部分向后延伸到原始字符串本身的主体中。事实上，为了尽量减少添加的字符数，这必须是结束回到字符串本身的最大可能字符数。我们可以在这里看到:
| original string | | extra characters |
| overlap |
现在，我们的 KMP 步骤会发生什么？好吧，当在自身内部查找字符串的反转时，KMP 将在整个字符串中工作时始终保持尽可能长的匹配。这意味着当 KMP 到达字符串的末尾时，它维护的匹配部分将是最长的可能匹配，因为 KMP 只会在失败时向前移动候选匹配的起点。因此，我们有最长的可能重叠，因此我们将在最后获得所需的尽可能短的字符数。
我不是 100% 确定这是否有效，但似乎在我可以处理的所有情况下都有效。正确性证明似乎是合理的，但它有点手摇，因为正式的基于 KMP 的证明可能有点棘手。
希望这对您有所帮助!
关于string - 给定一个单词，将其转换为回文，并添加最少的字母，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9649476/