algorithm - 从给定的单词做回文

Question

我已经给出了喜欢的词abca。我想知道我需要添加多少个字母才能使其成为回文。在这种情况下它是 1，因为如果我添加 b，我得到abcba.

Answer 1

首先，让我们考虑一个低效的递归解决方案：

假设字符串的形式为aSb，其中a和b是字母，并且S是子字符串。

如果a==b，那么f(aSb) = f(S)。

如果a!=b，那么您需要添加一个字母：要么a在末尾添加一个，要么b在前面添加一个。我们需要尝试两者，看看哪个更好。所以在这种情况下，f(aSb) = 1 + min(f(aS), f(Sb))。

这可以使用递归函数来实现，该函数将花费指数时间来运行。

为了提高性能，请注意这个函数只会被原始字符串的子字符串调用。只有 O(n^2) 个这样的子串。因此，通过记忆这个函数的结果，我们将花费的时间减少到 O(n^2)，代价是 O(n^2) 空间。

Answer 2

基本算法如下所示：

• 遍历字符串的一半并检查字符是否存在于另一端的适当位置（即，如果有，abca则第一个字符是 ana并且字符串也以 结尾a）。
  • 如果它们匹配，则继续下一个字符。
  • 如果它们不匹配，请注意需要添加一个字符。

请注意，您只能在字符匹配时从末尾移动 backwords。例如，如果字符串是，abcdeffeda则外部字符匹配。这时我们需要考虑bcdeffed。外部字符不匹配，因此b需要添加 a。但是我们不想继续cdeffe（即删除/忽略两个外部字符），我们只是删除b并继续查看cdeffed. 与此类似c，这意味着我们的算法只返回2字符串修改而不是更多。