0

可能的重复：
寻找回文的算法

如何在字符串中找到所有回文，例如：

“AA BB AA TTT AA BB”

我知道如何在单个字符串中找到回文，如果我通过删除“”字符来合并这些字符串，我仍然可以找到回文......但如果我这样做，我如何重建原始单词......

或者是否有任何其他可能需要更少时间的方法......任何线索......？

4

3 回答 3

4

编辑：我假设您要问的是：给定一串字符，我如何确定所有可能的回文子串？

您可以从单个字符开始构建，这些字符本身就是微不足道的回文，然后考虑所有长度为 2 的子字符串，然后是所有长度为 3 的子字符串。

幸运的是，回文具有递归关系，因此如果您删除了第一个和最后一个字母，您仍然必须有一个回文。因此，如果一个长度为 4 的字符串是回文串（如 ABBA），那么去掉第一个和最后一个字符的子串（'BB'）也一定是回文串。

考虑一个动态规划解决方案来计算任何给定的字符串，因为上面定义的递归关系满足 DP 的最佳子问题要求。

于 2013-01-18T20:07:21.487 回答
0

问题实际上归结为查找所有子字符串。在您遍历字符串中的每个“单词”（AA、BB、AA、TTT 等）之后，您可以将每个单词视为单个字符，因此 map AA->a、BB->b等TTT->t，现在从您的示例中新“减少”字符串是abatab. 查找所有子串abatab并检查每个子串是否是回文，如果是，则可以通过在地图中查找单词来打印出原始字符串。一个例子是aba -> AABBAA。

如果你的单词不是全部由相同的字母组成，问题就会变得更有趣。如果你有AB BA. 在这种情况下AB和BA不是回文，但它们的串联是ABBA。

于 2013-01-18T20:13:48.653 回答
0

SauceMaster 的回答描述了如何解决回文问题。

我只想回答这个问题。

我知道如何在单个字符串中找到回文，如果我通过删除“”字符来合并这些字符串，我仍然可以找到回文......但如果我这样做了，我如何重建原始单词？

首先复制字符串。

于 2013-01-18T20:14:45.603 回答