如何计算将字符串转换为回文式所需的字符数？

如何计算将字符串转换为回文式所需的字符数？

注意：这只是出于好奇。Dav提出了一种算法，可以将该算法修改为DP算法，以便轻松地在O（n ^ 2）时间和O（n ^
2）空间中运行（并且也许O（n）具有更好的簿记）。

当然，如果您决定更改允许的 *** 作，那么这种“幼稚”算法实际上可能会派上用场。

---

这是一个“天真”的算法，通过聪明的簿记可以使其更快。

给定一个字符串，我们猜测所得回文的中间位置，然后尝试计算使该字符串成为该中间周围的回文位置所需的插入数。

如果字符串的长度为n，则可能有2n + 1个中间（每个字符，在两个字符之间，紧接在字符串之前和之后）。

假设我们考虑一个中位数，它给我们两个字符串L和R（一个到左，一个到右）。

如果我们使用插入，我相信现在可以使用最长公共子序列算法（这是一种DP算法）来创建一个同时包含L和R的反向字符的“超级”字符串，请参见最短公共超序列。

选择中间，它会为您提供最小的插入数。

我相信这是O（n ^ 3）。（注意：我没有尝试证明它是真的）。