最长回文子串

在给定字符串中找到也是回文的最长子串被称为最长回文子串问题。回文是指正读反读都相同的单词、短语、数字或其他字符串。例如，“racecar”和“level”都是回文。

给定字符串中最长的连续回文子串被称为“最长回文子串”。换句话说，它是原始字符串中正读反读都相同的最长字符组。此子串的长度可以是奇数或偶数。

在计算机科学中，在给定字符串中寻找最长回文子串是一个常见问题，通常使用各种方法和策略来解决。

示例

最长回文子串的朴素方法

确定最长回文子串的基本方法是创建给定字符串的所有可能子串，并确定每个子串是否为回文。首先可以生成长度为 1、2 等直至输入字符串长度的所有可能子串。我们确定每个子串是否为回文，并记录目前为止最长回文的长度。

朴素方法的时间复杂度为 O(n^3)，这使其效率低下，尤其是对于大型字符串。它需要 O(n^2) 时间来生成所有可能的子串，并需要 O(n) 时间来确定每个子串是否为回文。

可以使用这种方法找到最长回文子串；但是，对于较大的输入，建议使用更有效的方法，例如前面描述的动态规划方法。

Java 代码

输出

"bab" or "aba" (both are possible; one will be printed as output)

通过比较字符串开头和结尾的字符，直到它们在中间相遇，isPalindrome 函数确定给定字符串 s 是否为回文。

最长回文朴素函数使用嵌套循环生成所有可能的子串，并确定每个子串是否为回文。它会跟踪目前为止最长的回文，并返回结果。

当代码执行时，将打印“bab”或“aba”这两个子串中的一个作为输出，因为它们都是输入字符串“babad”中最长回文子串的有效答案。尽管存在比朴素方法更有效的方法来获得答案，但它仍然应该产生正确的结果。

在 Python 中

输出

aaa

该程序包含用于确定字符串是否为回文以及最长回文子串长度的函数。is_palindrome 函数通过将其与反向字符串进行比较来检查字符串的回文状态。longest_palindrome_naive 函数创建输入字符串的所有子串，并确定每个子串是否为回文，同时跟踪找到的最长子串。该函数返回最长的回文子串。在示例用法中，演示了查找“baaab”的最长回文子串，它本身就是输入字符串，因为它是一个回文。该代码非常复杂，对于较长的字符串，最好采用更好的技术。

使用动态规划

在 Java 中

输出

"bab" or "aba" (both are possible)

上述 Java 代码实现了动态规划方法，以识别输入字符串 s 中最长的回文子串。为了节省时间，longestPalindromeDP 方法将子串是否为回文存储在一个名为 dp 的二维布尔数组中。所有单个字符和所有相邻字符对最初都为 dp 初始化。然后，迭代检查较大的子串，并根据当前子串是否为回文更新数组。该函数使用 start 和 maxLength 记录发现的最长回文子串。最终输出是从 start 到 start + maxLength - 1 的子串。动态规划方法显著提高了效率，并将问题的时间复杂度降低到 O(n^2)。

在 Python 中

输出

"aaaa"  (the longest palindromic substring in "baaaac")

Python 函数 longest_palindrome_dp 使用动态规划来查找输入字符串“baaaac”中最长的回文子串。该算法初始化一个名为 dp 的二维布尔数组，以保存子串是否为回文。它识别两个字符的回文，并将所有长度为 1 的子串标记为回文。为了确定当前子串是否为回文，它根据较小的子串重复检查较长的子串。该函数检查回文并更新 start 索引和 max_length 变量，以记录目前为止识别到的最长回文子串。一旦动态规划表完成，该函数将最长回文子串作为 start 到 start + max_length 返回。在此特定实例中，它将“a”识别为“baaaac”中最长的回文子串。动态规划方法确保该问题具有 O(n^2) 的有效时间复杂度，使其成为较长输入字符串的首选解决方案。