5. 最长回文子串

问题描述

给定一个字符串 s，找到 s 中最长的回文子串。

示例：

输入: "babad"
输出: "bab" 或 "aba"

输入: "cbbd"
输出: "bb"

算法思路

方法一：动态规划（DP 数组）

1. 状态定义：
   • dp[i][j] 表示子串 s[i..j] 是否为回文串。
2. 状态转移：
   • 当 s[i] == s[j] 且子串长度 ≤ 2 时，必为回文串。
   • 当 s[i] == s[j] 且子串长度 > 2 时，dp[i][j] = dp[i+1][j-1]。
   • 当 s[i] != s[j] 时，dp[i][j] = false。
3. 遍历顺序：
   • 按子串长度从小到大遍历，确保状态转移时 dp[i+1][j-1] 已计算。
4. 记录结果：
   • 当 dp[i][j] 为 true 时，更新最长回文子串的起始位置和长度。

方法二：中心扩展法（空间优化）

1. 核心思想
   遍历所有可能的回文中心（单个字符或两个字符之间），从中心向两边扩展，判断是否形成回文子串。

2. 中心点计算

   • 长度为 n 的字符串有 2n-1 个中心：
     • n 个单字符中心（如 "a" 的中心是 a）
     • n-1 个双字符中心（如 "aa" 的中心在两个 a 之间）

3. 扩展规则

   • 设中心索引为 center（范围 [0, 2n-2]）
   • 左边界 left = center / 2
   • 右边界 right = left + center % 2
   • 向两边扩展：left-- 和 right++，直到字符不匹配或越界

代码实现

方法一：动态规划（DP 数组）

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) return "";
        
        int n = s.length();
        boolean[][] dp = new boolean[n][n]; // dp[i][j] 表示 s[i..j] 是否为回文串
        int maxLen = 1;      // 最长回文子串长度
        int start = 0;       // 最长回文子串起始位置
        
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        
        // 按子串长度从小到大遍历（从 2 到 n）
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1; // 子串结束位置
                
                // 首尾字符相同
                if (s.charAt(i) == s.charAt(j)) {
                    // 子串长度 ≤ 2 或 内部子串是回文串
                    if (len == 2 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        
                        // 更新最长回文子串信息
                        if (len > maxLen) {
                            maxLen = len;
                            start = i;
                        }
                    }
                }
                // 首尾字符不同，不是回文串（dp[i][j] 默认 false，可省略显式赋值）
            }
        }
        return s.substring(start, start + maxLen);
    }
}

方法二：中心扩展法（空间优化）

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) return "";
        
        int n = s.length();
        int start = 0;      // 最长回文子串起始位置
        int maxLen = 1;     // 最长回文子串长度
        
        // 遍历所有可能的中心点（共 2n-1 个）
        for (int center = 0; center < 2 * n - 1; center++) {
            // 根据中心点计算左右起始位置
            int left = center / 2;
            int right = left + center % 2; // 奇数中心：left=right；偶数中心：right=left+1
            
            // 从中心向两边扩展
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                // 计算当前回文子串长度
                int curLen = right - left + 1;
                
                // 更新最长回文子串信息
                if (curLen > maxLen) {
                    maxLen = curLen;
                    start = left;
                }
                
                // 继续扩展
                left--;
                right++;
            }
        }
        return s.substring(start, start + maxLen);
    }
}

算法分析

• 时间复杂度：
  • 两种方法均为 O(n²)，动态规划嵌套两层循环，中心扩展法遍历 2n-1 个中心点。
• 空间复杂度：
  • 动态规划：O(n²)，需要二维 DP 数组。
  • 中心扩展：O(1)，仅使用常数空间。

算法过程

输入：s = "babad"

1. 动态规划：
   • 初始化：所有单个字符为回文（dp[0][0]、dp[1][1]等为 true）
   • 长度 2：
     • [0,1]：“ba” → 'b'!='a' → 不更新
     • [1,2]：“ab” → 'a'!='b' → 不更新
     • [2,3]：“ba” → 'b'!='a' → 不更新
     • [3,4]：“ad” → 'a'!='d' → 不更新
   • 长度 3：
     • [0,2]：“bab” → 'b'=='b' 且 dp[1][1]=true → 更新（maxLen=3, start=0）
     • [1,3]：“aba” → 'a'=='a' 且 dp[2][2]=true → 更新（长度相同，不覆盖）
   • 结果："bab" 或 "aba"

输入：s = "cbbd"

1. 中心扩展：
   • 中心点 0（left=0, right=0）：“c”（长度 1）
   • 中心点 1（left=0, right=1）：“cb” → 不匹配
   • 中心点 2（left=1, right=1）：“b”（长度 1）
   • 中心点 3（left=1, right=2）：“bb” → 匹配（长度 2）→ 更新（maxLen=2, start=1）
   • 中心点 4（left=2, right=2）：“b”（长度 1）
   • 中心点 5（left=2, right=3）：“bd” → 不匹配
   • 结果："bb"

测试用例

public static void main(String[] args) {
    Solution solution = new Solution();
    
    // 测试用例1: 标准示例
    String s1 = "babad";
    System.out.println("Test 1: " + solution.longestPalindrome(s1)); // "bab" 或 "aba"
    
    // 测试用例2: 连续相同字符
    String s2 = "cbbd";
    System.out.println("Test 2: " + solution.longestPalindrome(s2)); // "bb"
    
    // 测试用例3: 全相同字符
    String s3 = "aaaa";
    System.out.println("Test 3: " + solution.longestPalindrome(s3)); // "aaaa"
    
    // 测试用例4: 单字符
    String s4 = "a";
    System.out.println("Test 4: " + solution.longestPalindrome(s4)); // "a"
    
    // 测试用例5: 空字符串
    String s5 = "";
    System.out.println("Test 5: " + solution.longestPalindrome(s5)); // ""
    
    // 测试用例6: 长回文串
    String s6 = "forgeeksskeegfor";
    System.out.println("Test 6: " + solution.longestPalindrome(s6)); // "geeksskeeg"
}

关键点

1. 动态规划核心：
   • 状态转移依赖内部子串结果（dp[i+1][j-1]）。
   • 按子串长度从小到大遍历确保依赖项已计算。
2. 中心扩展核心：
   • 统一处理奇偶长度回文串（通过 center % 2 控制）。
   • 实时计算回文长度并更新最优解。
3. 边界处理：
   • 空字符串直接返回空串。
   • 单字符字符串返回自身。

常见问题

1. 动态规划中为什么按长度遍历？
   确保计算 dp[i][j] 时，其依赖的子问题 dp[i+1][j-1] 已解决。

2. 中心扩展法如何避免重复计数？
   每个中心点独立扩展，自然覆盖所有不重复的回文子串。

3. 两种方法如何选择？

   • 动态规划：思路直接，但空间占用高。
   • 中心扩展：空间效率高，代码更简洁。