最长回文子串（动态规划解法）

我将为您详细讲解最长回文子串问题的动态规划解法。

问题描述
给定一个字符串s，找到s中最长的回文子串。回文串是正着读和反着读都一样的字符串。

示例
输入：s = "babad"
输出："bab" 或 "aba"

解题思路

1. 定义状态
我们定义dp[i][j]表示字符串s从索引i到j的子串是否是回文串。

• 如果dp[i][j] = true，表示s[i...j]是回文串
• 如果dp[i][j] = false，表示s[i...j]不是回文串

2. 状态转移方程
对于任意子串s[i...j]，判断其是否为回文串需要满足：

• 基本情况1：当i = j时，单个字符肯定是回文串
• 基本情况2：当j = i + 1时，两个相邻字符，只有当s[i] = s[j]时才是回文串
• 一般情况：当j > i + 1时，s[i...j]是回文串当且仅当：
  • s[i] = s[j]（首尾字符相同）
  • 且s[i+1...j-1]是回文串（内部子串是回文串）

用状态转移方程表示：

• 如果i = j：dp[i][j] = true
• 如果j = i + 1：dp[i][j] = (s[i] == s[j])
• 如果j > i + 1：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

3. 初始化
对角线上的元素dp[i][i] = true，因为单个字符都是回文串。

4. 遍历顺序
由于dp[i][j]依赖于dp[i+1][j-1]，即左下角的值，所以我们需要：

• 按子串长度从小到大遍历
• 先遍历子串长度，再遍历起始位置

5. 记录结果
在填充dp表的过程中，记录找到的最长回文子串的起始位置和长度。

详细实现步骤

让我们以s = "babad"为例：

步骤1：初始化
创建5x5的dp表，所有对角线元素设为true：

   b a b a d
b  T
a    T
b      T
a        T
d          T

步骤2：处理长度为2的子串
检查所有相邻字符对：

• "ba"：b≠a → false
• "ab"：a≠b → false
• "ba"：b≠a → false
• "ad"：a≠d → false

步骤3：处理长度为3的子串

• "bab"：首尾b=b，且中间"a"是回文 → true
• "aba"：首尾a=a，且中间"b"是回文 → true
• "bad"：首尾b≠d → false

此时找到"bab"和"aba"，长度3

步骤4：处理长度为4的子串

• "baba"：首尾b≠a → false
• "abad"：首尾a≠d → false

步骤5：处理长度为5的子串

• "babad"：首尾b≠d → false

最终最长回文子串是"bab"或"aba"。

代码实现

def longestPalindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s
    
    # 初始化dp表
    dp = [[False] * n for _ in range(n)]
    
    # 所有单个字符都是回文
    for i in range(n):
        dp[i][i] = True
    
    max_len = 1
    start = 0
    
    # 按子串长度遍历
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j]:
                if length == 2:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i + 1][j - 1]
            else:
                dp[i][j] = False
            
            # 更新最长回文子串
            if dp[i][j] and length > max_len:
                max_len = length
                start = i
    
    return s[start:start + max_len]

复杂度分析

• 时间复杂度：O(n²)，需要填充n²大小的dp表
• 空间复杂度：O(n²)，需要n²大小的dp表

优化思路
可以通过中心扩展法将空间复杂度优化到O(1)，但动态规划解法的思路更加清晰直观，适合理解回文子串的判断逻辑。