动态规划中等2 种解法

#5最长回文子串

返回字符串中长度最长的回文连续子串。

#字符串#动态规划#中心扩展

解题主线

每个回文串都可从一个字符中心或两个字符之间向两侧扩展。

区间 [left, right] 为回文，当且仅当两端相同且内部区间为回文；长度不超过 2 时内部为空。

解法 1：中心扩展

枚举 2n-1 个可能中心，分别向两侧扩展并记录最长闭区间。

时间复杂度

O(n²)

空间复杂度

O(1)

5. 最长回文子串 · 中心扩展

java

final class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s == null ? "" : s;
        int bestStart = 0;
        int bestLength = 1;
        for (int center = 0; center < s.length(); center++) {
            int odd = expand(s, center, center);
            int even = expand(s, center, center + 1);
            int length = Math.max(odd, even);
            if (length > bestLength) {
                bestLength = length;
                bestStart = center - (length - 1) / 2;
            }
        }
        return s.substring(bestStart, bestStart + bestLength);
    }

    private int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length()
                && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

枚举 2n-1 个可能中心，分别向两侧扩展并记录最长闭区间。

解法 2：区间动态规划

自短区间到长区间判断回文性，并保存目前最长区间。

时间复杂度

O(n²)

空间复杂度

O(n²)

5. 最长回文子串 · 区间动态规划

java

final class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s == null ? "" : s;
        int n = s.length();
        boolean[][] palindrome = new boolean[n][n];
        int bestStart = 0;
        int bestLength = 1;
        for (int left = n - 1; left >= 0; left--) {
            for (int right = left; right < n; right++) {
                palindrome[left][right] = s.charAt(left) == s.charAt(right)
                        && (right - left < 2 || palindrome[left + 1][right - 1]);
                int length = right - left + 1;
                if (palindrome[left][right] && length > bestLength) {
                    bestStart = left;
                    bestLength = length;
                }
            }
        }
        return s.substring(bestStart, bestStart + bestLength);
    }
}

自短区间到长区间判断回文性，并保存目前最长区间。

边界与易错点

奇数与偶数长度回文需要分别选择中心。
动态规划必须按 left 从右向左计算，保证 dp[left + 1][right - 1] 已知。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

medium/Q005_longestPalindrome.java