问题标签 [palindrome]

我正在尝试解决 Cormem 的算法介绍第 3 版（第 405 页）中的动态编程问题，该问题提出以下问题：

回文是一些字母表上的非空字符串，向前和向后读取相同。回文的例子都是长度为 1 的字符串，, civic, racecar, and aibohphobia (fear of palindromes)。

给出一个有效的算法来找到作为给定输入字符串的子序列的最长回文。例如，给定输入 character，您的算法应该返回carac。

好吧，我可以通过两种方式解决它：

第一个解决方案：

字符串的最长回文子序列 (LPS) 只是其自身的最长公共子序列及其反向。（我在解决了另一个要求序列的最长递增子序列的相关问题后构建了这个解决方案）。由于它只是一个 LCS 变体，它还需要 O(n²) 时间和 O(n²) 内存。

第二种解决方案：

第二种解决方案更详细一些，但也遵循通用 LCS 模板。它来自以下重复：

计算 lps 长度的伪代码如下：

如果我想有效地构造lps，它仍然需要 O(n²) 时间和内存（因为我需要桌子上的所有单元格）。分析相关问题，例如 LIS，可以用 LCS 以外的方法解决，用更少的内存（LIS 可以用 O(n) 内存解决），我想知道是否可以用 O(n) 内存解决它，也。

LIS 通过链接候选子序列来实现这个界限，但是对于回文则更难，因为这里重要的不是子序列中的前一个元素，而是第一个元素。有谁知道是否可以做到，或者以前的解决方案内存是最优的吗？

可能重复：
检查字符串是否有回文

你好专家。有人问我，是否可以仅在 C++/Java 中的一行代码中找到一个字符串是否是另一个字符串的回文。

如果是，那么如何？

谁能回答。谢谢你的看法。

1. 我可以得到一个递归 Prolog 谓词，它有两个参数，称为 reverse，它返回一个列表的倒数：

   示例查询和预期结果：

   /li>

2. palindrome如果给定列表是回文，则调用两个参数的递归 Prolog 谓词，该谓词返回 true。

   具有预期结果的示例查询：

   /li>

我正在（为了好玩）编写一个可以识别回文的脚本。到目前为止，我在“Kayak”、“Racecar”、“Anna”、“A man a plan a canal Panama”方面取得了成功：但后一个短语的变体，如“amanaplana canalpan ama”给我带来了问题。

附带说明：我确实知道使用 PCRE 会让事情变得更容易，但我并不精通它，我的主要目标之一是了解检查回文背后的算法。

我很感激有关以下方面的回应：

• 我遇到的错误的识别。
• 关于如何改进代码的建议（如果我可以在不诉诸 $count 或 $scan_count 的情况下使事情正常进行，在我看来，这似乎是相对业余的）。

提前致谢。

我试图在一个字符串中找到最长的回文。蛮力解决方案需要 O(n^3) 时间。我读到有一个使用后缀树的线性时间算法。我熟悉后缀树并且很乐意构建它们。你如何使用构建的后缀树来找到最长的回文。

这是一个面试问题（再次）。

给定一个单连接链表，找出链表中最大的回文数。（你可以假设回文的长度是偶数）

我采用的第一种方法是使用堆栈——我们从一开始就遍历列表并不断推入字母。每当我们发现堆栈顶部的字母与链表上的下一个字母相同时，开始弹出（并增加链表指针）并设置匹配的字母数。在我们发现不匹配后，将您从堆栈中弹出的所有字母推回，并继续您的推入和弹出操作。这种方法的最坏情况复杂度将是 O(n2) 例如，当链表只是相同字母的字符串时。

为了提高空间和时间复杂度（通过一些常数因素），我建议将链表复制到一个数组中，并在数组中找到最大的回文数，这又需要 O(n2) 时间复杂度和 O(n) 空间复杂度。

有什么更好的方法可以帮助我吗？:(

这是我用Java编写的代码...除了这个之外还有什么有效的方法..我们可以进一步优化这段代码吗？

我在序言中尝试了这个回文程序，逻辑有效，但写操作不起作用。那么代码中的问题是什么？

佩林（列表 1）：- findrev（列表 1，[]，列表 2），比较（列表 1，列表 2）。

我想找到可以通过两个 3 位数字相乘得到的最大回文数。

我从 a 和 b 都为 999 开始，每次乘法都会减少 a 和 b。

结果出现了 698896、289982、94249、69696...，其中 698896 是第一个数字。目前我仍在试图弄清楚我错过了什么。

我正在尝试将文本框中字符串中的字符添加到我的堆栈中，

到目前为止，这是我的代码：

我来自 LinkedStack 的推送和弹出方法

getnext() 方法来自另一个名为 listnodes 的包

当我将打印更改为 + c 时，我的字符串中的所有字符都会打印出来，但是当它是 myStack 时，它现在给了我一个超出索引范围错误的字符串。

有人知道我错过了什么吗？