最长回文串

在本教程中，我们将学习如何编写 Python 程序来查找 Python 中的最长回文子串。在这个问题中，我们给出了一个字符串，我们需要找到该字符串中的最长回文子串。让我们通过以下示例来理解。

示例 - 1

示例 - 2

我们可以使用各种方法来解决这个问题。让我们看看下面的解决方案。

朴素方法

在这种简单的方法中，我们检查每个子串是否是回文串，优先检查长度较长的子串。以下是实现此想法的步骤。

• 创建给定字符串的子串，以便优先生成较长的子串。
• 为了实现这一点，实现一个循环，其中迭代器“LEN”从给定字符串的长度递减到 1，其中“N”表示给定字符串的长度。
• 执行嵌套循环并定义一个指示子串起始索引的迭代器“j”。
• 提取从索引“j”开始到“j + LEN”结束的子串。
• 如果提取的子串是回文串，则返回它，因为它代表具有最小起始索引的最长可能回文子串。

让我们来实现 Python 代码 -

示例 -

输出

"bab"

解释 -

首先，我们定义一个 is_palindrome(s) 函数，它检查给定的字符串 `s` 是否是回文串。它通过将原始字符串与其反向字符串进行比较来实现。如果它们相同，则返回 `True`，表示字符串是回文串；否则返回 `False`。

然后我们定义 longest_palindrome_substring(input_str) 函数来查找输入字符串 `input_str` 中的最长回文子串。

它遵循我们之前定义的步骤。

• 我们计算输入字符串的长度并将其存储在变量 `n` 中。
• 然后初始化一个空字符串 longest_palindrome` 来存储找到的最长回文子串。
• 我们运行一个从输入字符串长度 (`n`) 递减到 1 的循环。它代表我们将生成的子串的长度，从最长的可能长度递减到长度 1。
• 然后我们运行第二个循环，对于 range(n - length + 1) 中的 start_index，它会遍历给定 `length` 的子串的可能起始索引。由于我们想要长度为 `length` 的子串，我们需要确保起始索引不会超过 `n - length`。
• 提取从当前 `start_index` 开始，长度为 `length` 的子串。
• 检查 `substring` 是否是回文串（使用 `is_palindrome` 辅助函数），以及它的长度是否大于到目前为止找到的 `longest_palindrome` 的长度。
• 如果上述条件满足，则将 `longest_palindrome` 更新为当前的 `substring`。
• 在两个循环完成后，返回 `longest_palindrome`，它代表输入字符串中最长的回文子串。
• 在示例用法中，`input_str = "babad"`，该函数返回最长回文子串“bab”，然后将其作为输出打印。

查找回文的可能首尾字符

概念是确定字符串中每个字符的回文潜在最后一个字符。然后，验证以该潜在最后一个字符结尾的子串是否是回文串，并相应地更新回文串的长度。

以下是实现此概念的步骤。

• 运行一个循环来遍历字符串中的每个字符。
• 在此循环内，运行另一个嵌套循环以检查是否有其他字符与当前字符相同。
• 如果找到匹配的字符，则这两个字符可能构成潜在回文子串的首尾字符。
• 存储此子串并检查它是否是迄今为止找到的最长回文串。
• 如果确实是最长回文串，则存储它并继续迭代剩余字符以查找其他潜在回文串。

一旦完成所有迭代，函数应返回在过程中找到的最长回文子串。此子串代表给定输入字符串中最长的回文串。

让我们理解以下示例 -

示例 -

输出

"bab"

解释 -

• 函数 longestPalSubstr(s) 以字符串 s 作为输入，并找到其中的最长回文子串。
• 变量 longest 用于存储迄今为止找到的最长回文子串。
• 第一个循环（for i in range(n)）迭代输入字符串中的每个字符。
• 第二个循环（for j in range(n-1, i, -1)）从字符串末尾向当前字符 i 反向迭代。
• 在嵌套循环中，代码检查索引 i 和 j 处的字符是否相同。如果它们相同并且当前子串的长度大于迄今为止找到的最长回文串的长度，它会检查子串及其反向是否相等。如果相等，它会更新最长回文串。
• 在两个循环完成后，代码打印最长回文子串。
• 如果未找到最长回文子串，则返回输入字符串的第一个字符。
• 示例用法是使用 stri = "babad"，代码打印最长回文子串 "bab"。

使用动态规划的最长回文子串

此方法的核心概念是利用子串 [i, j] 的回文状态知识来确定子串 [i-1, j+1] 的状态。如果子串从 i 到 j 不是回文串，那么子串从 i-1 到 j+1 也不是回文串。反之，如果 str[i-1] 和 str[j+1] 相同，那么子串从 i-1 到 j+1 就是回文串。

为了应用这个想法，我们创建一个二维表（称之为 'table'），它存储子串 str[i . . . j] 的状态。然后我们检查长度从 1 到 N 的子串。对于每个长度，我们检查从每个字符 'i' 开始的所有可能的子串，并使用上述逻辑确定它是否是回文串。形成的最长回文串的长度将是所需的答案。

让我们理解以下示例 -

示例 -

输出

bab

解释 -

• 函数 longest_palindromic_substring(input_str) 以字符串 input_str 作为输入并返回最长回文子串。
• 它创建了一个二维表 'table' 来存储子串的状态。每个单元格 table[i][j] 如果从 input_str[i] 到 input_str[j] 的子串是回文串，则为 True。
• 首先，它将所有长度为 1 的子串标记为回文串（因为单个字符是回文串）。
• 接下来，它检查长度为 2 的子串，如果两端的字符相同，则将其标记为回文串。
• 然后，它使用嵌套循环检查长度大于 2 的子串。对于每个长度，它遍历从每个索引 'i' 开始的所有可能的子串，并检查第一个和最后一个字符是否相同，以及它们内部的子串（i+1 到 j-1）是否是回文串。如果两个条件都满足，则将子串标记为回文串。
• 在此过程中，它会跟踪找到的最长回文子串的起始索引和长度。
• 最后，它使用起始索引和长度返回最长回文子串。
• 示例用法使用 input_str = "babad" 测试函数，并打印最长回文子串 "bab"。