15

这是一个非常有趣的面试问题：

给定一个单词，将最少数量的字母附加到它以将其转换为回文。

例如，如果“hello”是给定的字符串，结果应该是“hellolleh”。如果给出“coco”，结果应该是“cococ”。

我能想到的一种方法是将字符串的反向附加到原始字符串的末尾，然后尝试从末尾消除多余的字符。但是，我无法弄清楚如何有效地做到这一点。有没有人有任何想法？

4

4 回答 4

10

好的！这是我的第二次尝试。

这个想法是，我们想知道在追加额外字符以完成回文时，可以重复使用字符串末尾的多少字符。为了做到这一点，我们将使用 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 的证明可能有点棘手。

希望这可以帮助！

于 2012-03-11T09:02:04.887 回答
5

为了回答，我会采取这种天真的方法：

  1. 当我们需要 0 个字符时？当字符串是回文时
  2. 当我们需要 1 个字符时？当除了第一个字符串是回文
  3. 当我们需要 2 个字符时？当除了 2 个起始字符之外，字符串是回文
  4. 等等等等……

所以一个算法可以是

  for index from 1 to length
   if string.right(index) is palindrome
    return string + reverse(string.left(index))
   end
  next

编辑

我不是一个 Python 人，但上述伪代码的简单实现可能是

>>> def rev(s): return s[::-1]
... 
>>> def pal(s): return s==rev(s)
... 
>>> def mpal(s):
...  for i in range(0,len(s)):
...   if pal(s[i:]): return s+rev(s[:i])
... 
>>> mpal("cdefedcba")
'cdefedcbabcdefedc'
>>> pal(mpal("cdefedcba"))
True
于 2012-03-11T09:21:03.763 回答
4

简单的线性时间解。

让我们称我们的字符串为 S。

令 f(X, P) 为 X 和 P 的最长公共前缀的长度。计算 f(S[0], rev(S)), f(S[1], rev(S)), ...其中 S[k] 是从位置 k 开始的 S 的后缀。显然，您想选择最小 k 使得 k + f(S[k], rev(S)) = len(S)。这意味着您只需在末尾附加 k 个字符。如果 k 为 0，则刺痛已经是回文。如果 k = len(S)，那么您需要附加整个反向。

我们需要快速计算所有 S[i] 的 f(S[i], P)。这是棘手的部分。创建 S 的后缀树。遍历树并用 P 的最长公共前缀的长度更新每个节点。叶子处的值对应于 f(S[i], P)。

于 2012-03-11T12:07:45.373 回答
2

首先创建一个函数来测试字符串的回文性，记住“a”和“aa”是回文。它们是回文，对吧？？？

如果输入是回文，则返回它（需要添加 0 个字符） 从 x[length] 循环到 x[1] 检查字符串 x[i]..x[length] 的子集是否是回文，找到最长的回文。

从最长回文之前的输入字符串中取出子字符串，将其反转并将其添加到末尾应该通过附加来生成最短回文。

coco => c+oco => c+oco+c

mmmeep => mmmee+p => mmmee+p+eemmm

于 2012-03-11T09:17:37.700 回答