5.最长回文子串

题目描述

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

示例 1

输入: s = "babad"
输出: "bab"

示例 2

输入: s = "cbbd"
输出: "bb"

解题思路一：中心扩展

回文以中心对称。以每个字符为奇数中心、每对相邻字符为偶数中心，向两侧扩展比较。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String s = scanner.next();

        Solution solution = new Solution();
        String result = solution.longestPalindrome(s);
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;
        int start = 0, maxLen = 1;
        for (int i = 0; i < n; i++) {
            int[] p1 = expand(s, i, i);       // 奇数中心
            int[] p2 = expand(s, i, i + 1);   // 偶数中心
            int len1 = p1[1] - p1[0] + 1;
            int len2 = p2[1] - p2[0] + 1;
            if (len1 > maxLen) { start = p1[0]; maxLen = len1; }
            if (len2 > maxLen) { start = p2[0]; maxLen = len2; }
        }
        return s.substring(start, start + maxLen);
    }

    private int[] expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
        return new int[]{l + 1, r - 1};
    }
}

解题思路二：动态规划

设 dp[i][j] 表示 s[i..j] 是否为回文。

转移：s[i] == s[j] 且 dp[i+1][j-1] 为真，则 dp[i][j] 为真。长度为 1 或 2 的区间单独处理为真。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String s = scanner.next();

        Solution solution = new Solution();
        String result = solution.longestPalindrome(s);
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for(int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        int l = 0, r = 0;
        for(int j = 1; j < len; j++) {
            for(int i = 0; i < j; i++) {
                if(s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                }else {
                    if(j - i < 3) {
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if(dp[i][j] && j - i >= r - l){
                    l = i;
                    r = j;
                }
            }
        }
        return s.substring(l, r + 1);
    }
}

复杂度分析

• 中心扩展：时间 O(n^2)，空间 O(1)。
• 动态规划：时间 O(n^2)，空间 O(n^2)。

中心扩展实现更简洁、空间最优；动态规划适合系统掌握回文判定的区间转移。