【LeetCode】动态规划—5. 最长回文子串（附完整Python/C++代码）

前言

回文字符串问题是字符串处理中的经典问题之一，尤其是寻找最长回文子串的问题。回文子串不仅在字符串理论中具有重要意义，还在自然语言处理、DNA序列分析等应用场景中有着广泛的使用。在处理回文子串问题时，动态规划提供了直观且有效的解决方案，可以通过递推公式解决复杂的子问题。

本文将介绍如何通过动态规划方法解决最长回文子串问题，并结合 Python 和 C++ 代码详细讲解每一步的实现逻辑。同时，还将展示如何利用中心扩展法来进一步优化空间复杂度，帮助你在面对实际问题时能选择合适的算法策略。

题目描述

基本思路

1. 问题定义

给定一个字符串 $s$ ，找到其中最长的回文子串。回文是指正读和反读相同的字符串。问题的目标是返回 $s$ 中最长的回文子串。

2. 理解问题和递推关系

要找到最长的回文子串，可以采用动态规划的方法。动态规划的核心思想是通过求解较小问题的解来构建较大问题的解。在这个问题中，我们可以通过判断一个较小的子串是否是回文，进而推导出更长的子串是否为回文。

设 $dp[i][j]$ 表示字符串 $s[i\dots j]$ 是否是回文串，那么状态转移方程为:

• 如果 $s[i]==s[j]$ ，且 $dp[i+1][j-1]$ 为真，则 $dp[i][j]=True$。
• 否则, $dp[i][j]=False$。

边界条件:

• 单个字符一定是回文串，因此 $dp[i][i]=$ True。
• 两个相邻相同的字符也是回文串，即如果 $s[i]==s[i+1]$ ，那么 $dp[i][i+1]=$ True。

3. 解决方法

3.1 动态规划方法

1. 初始化一个二维数组 $dp$ ，其中 $dp[i][j]$ 表示字符串 $s[i\dots j]$ 是否是回文串。
2. 初始化 $dp$ ，对于单个字符以及长度为 2 的字符串，直接设置为回文。
   3．通过动态规划计算长度大于 2 的子串是否为回文，并记录最长回文子串的起始位置和长度。
3. 返回最长回文子串。

3.2 中心扩展方法

1. 遍历字符串中的每一个字符，将其作为中心，尝试向外扩展，寻找最长的回文子串。
2. 每个字符可以作为中心扩展，考虑奇数长度的回文串；两个相邻字符也可以作为中心扩展，考虑偶数长度的回文串。

4. 进一步优化

• 中心扩展方法可以减少空间复杂度，因为不需要额外的二维数组来存储结果。该方法的时间复杂度为 $O\left(n^{\wedge }2\right)$ ，但空间复杂度优化为 $O(1)$ 。

5. 小总结

• 动态规划方法直观且易于理解，能够有效解决问题，但需要额外的空间存储中间结果，空间复杂度为 $O\left(n^{\wedge }2\right)$ 。
• 中心扩展方法更为简洁，通过遍历每一个字符并扩展来寻找回文子串，能够在时间昜杂度为 $O\left(n^{\wedge }2\right)$ 的同时优化空间复杂度到 $O(1)$ 。
• 通过选择适合的解决方案，可以平衡时间和空间复杂度，以解决不同规模的数据问题。

以上就是最长回文子串问题的基本思路。

代码实现

Python

Python3代码实现

class Solution:def longestPalindrome(self, s: str) -> str:n = len(s)if n < 2:return s# 初始化dp数组，dp[i][j]表示s[i...j]是否为回文dp = [[False] * n for _ in range(n)]start, max_len = 0, 1  # 记录最长回文子串的起始位置和长度# 单个字符是回文for i in range(n):dp[i][i] = True# 计算长度为2的回文子串for i in range(n - 1):if s[i] == s[i + 1]:dp[i][i + 1] = Truestart, max_len = i, 2# 动态规划计算长度大于2的回文子串for length in range(3, n + 1):for i in range(n - length + 1):j = i + length - 1if s[i] == s[j] and dp[i + 1][j - 1]:dp[i][j] = Truestart, max_len = i, length# 返回最长回文子串return s[start:start + max_len]

Python 代码解释

• 初始化：创建 dp 数组并将单个字符设置为回文串。
• 处理特殊情况：处理长度为2的回文串。
• 动态规划递推：对于每个长度大于2的子串，通过递推公式检查其是否为回文。
• 结果输出：根据 dp 数组中的结果，返回最长的回文子串。

Python代码进一步优化

class Solution:  def longestPalindrome(self, s: str) -> str:  if len(s) < 2:  return s  start, max_len = 0, 1  for i in range(len(s)):  # 获取奇数长度中心  len1 = self.expandAroundCenter(s, i, i)  # 获取偶数长度中心  len2 = self.expandAroundCenter(s, i, i + 1)  max_len_current = max(len1, len2)  if max_len_current > max_len:  max_len = max_len_current  # 更新最长回文子串的起始位置  start = i - (max_len - 1) // 2  return s[start:start + max_len]  def expandAroundCenter(self, s, left, right):  while left >= 0 and right < len(s) and s[left] == s[right]:  left -= 1  right += 1  return right - left - 1  # 计算回文长度

优化解析

• 中心扩展法：对每个字符（或字符之间）作为中心，逐渐向外扩展，检查字符是否相同以识别回文。
• expandAroundCenter函数：此函数负责在给定的中心向外扩展，并返回找到的回文的长度。
• 时间复杂度：整体时间复杂度为 $O\left(n^{\wedge }2\right)$，但常数因子较小，通常执行速度更快。
• 空间复杂度：这里只使用了少量附加的变量，因此为 $O(1)$。

通过这样的方式，我们能在保留算法逻辑的同时，提高其执行速度。

C++

C++代码实现

class Solution {
public:string longestPalindrome(string s) {int n = s.length();if (n < 2) return s;// 初始化dp数组，dp[i][j]表示s[i...j]是否为回文vector<vector<bool>> dp(n, vector<bool>(n, false));int start = 0, max_len = 1;  // 记录最长回文子串的起始位置和长度// 单个字符是回文for (int i = 0; i < n; ++i) {dp[i][i] = true;}// 计算长度为2的回文子串for (int i = 0; i < n - 1; ++i) {if (s[i] == s[i + 1]) {dp[i][i + 1] = true;start = i;max_len = 2;}}// 动态规划计算长度大于2的回文子串for (int len = 3; len <= n; ++len) {for (int i = 0; i + len - 1 < n; ++i) {int j = i + len - 1;if (s[i] == s[j] && dp[i + 1][j - 1]) {dp[i][j] = true;start = i;max_len = len;}}}// 返回最长回文子串return s.substr(start, max_len);}
};

C++ 代码解释

• 初始化：使用二维数组 dp 存储每个子串是否为回文，初始化单个字符和长度为2的回文子串。
• 递推公式：利用动态规划计算长度大于2的子串是否为回文，并记录最长回文子串的位置和长度。
• 返回结果：根据 dp 数组的值，返回找到的最长回文子串。

C++代码进一步优化

class Solution {  
public:  string longestPalindrome(string s) {  int n = s.length();  if (n < 2) return s;  int start = 0, max_len = 1;  for (int i = 0; i < n; ++i) {  // 计算奇数长度回文  int len1 = expandAroundCenter(s, i, i);  // 计算偶数长度回文  int len2 = expandAroundCenter(s, i, i + 1);  int max_current_len = max(len1, len2);  if (max_current_len > max_len) {  max_len = max_current_len;  // 更新最长回文子串的起始位置  start = i - (max_len - 1) / 2;  }  }  return s.substr(start, max_len);  }  private:  int expandAroundCenter(const string& s, int left, int right) {  while (left >= 0 && right < s.length() && s[left] == s[right]) {  --left;  ++right;  }  return right - left - 1;  // 返回回文长度  }  
};

优化解析

• 中心扩展法：对于每个字符（或每对相邻字符）作为潜在的回文中心，通过向两侧扩展来查找回文。
• expandAroundCenter 函数：负责扩展并返回找到的回文的长度。与原始方法相比，此方法减少了对额外空间（如 DP 表）的需求。
• 主循环：分别处理奇数长度和偶数长度的回文，更新最大长度和起始位置。

优点

• 空间复杂度：优化后的实现只使用 $O(1)$ 的额外空间，不需要动态规划的表，因此更高效。
• 简洁性：代码逻辑简化，使得理解、调试和维护变得更加容易。

通过这种方式，代码不仅执行速度更快，而且易于理解，同时保持相同的时间复杂度。

---

总结:

• 动态规划方法为解决最长回文子串问题提供了有效的途径。通过定义状态转移方程并逐步求解，我们能够快速找到最长回文子串。该方法的时间复杂度为 $O\left(n^{\wedge }2\right)$，空间复杂度为 $O\left(n^{\wedge }2\right)$。
• 通过中心扩展法，我们可以在同样的时间复杂度下将空间复杂度降低到 $O(1)$，这对于处理大规模字符串非常有帮助。
• 动态规划思想与中心扩展法各有优劣，如何选择取决于具体的应用场景与数据规模。在理解这些算法的同时，学会灵活应用将是解决问题的关键。