【Leetcode 5】最长回文字串 —— 动态规划

5. 最长回文字串

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

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

题目分析

经典动态规划问题，更多案例可见 Leetcode 动态规划详解

我们可以使用动态规划解决本题，解题思路：

1. 状态定义：dp[l][r]表示起点为i，终点为j的字串是否回文串
2. 状态转移方程：dp[l][r] = dp[l + 1][r - 1] && char[l] == char[r]，即dp[l + 1][r - 1]为回文串且i和j的字符相同

动态规划一般用于求解具有重叠子问题和最优子结构的问题，例如最长公共子序列、背包问题、最短路径等。重叠子问题指的是在求解问题的过程中，多次用到相同的子问题，最优子结构指的是问题的最优解可以通过子问题的最优解来构造

class Solution {
   
   
    /**
     * 状态转移方程：dp[l][r] = dp[l + 1][r - 1] && char[l] == char[r]
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
   
   
        if (s == null || s.length() < 2) {
   
   
            return s;
        }
        int n = s.length();
        //最长回文串的起点、终点和长度
        int maxStart = 0, maxEnd = 0, maxLen = 1;
        boolean[][] dp = new boolean[n][n];
        for (int r = 1; r < n; r++) {
   
   
            for (int l = 0; l < r; l++) {
   
   
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
   
   
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
   
   
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;
                    }
                }
            }
        }
        return s.substring(maxStart, maxEnd + 1);
    }
}