Leetcode 5. 最长回文子串

题目要求

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

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

示例 1：

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

示例 2：

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

解题思路

这道题用动态规划来解。

定义dp[i][j]表示从i到j的子串是否是回文串。

递推公式：

• 如果s.charAt(i) == s.charAt(j)，dp[i][j] = dp[i+1][j-1] || (j-i)<=2 （只有两个数字的情况）
• 如果s.charAt(i) != s.charAt(j)，肯定不能组成回文串，dp[i][j] = false

Java代码

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int res = 1, l = 0;
        for(int i = n-1; i >= 0; i--){
            for(int j = i+1; j < n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1] || (j-i) <= 2;
                    if(dp[i][j] && res < j-i+1){
                        res = j-i+1;
                        l = i;
                    }
                }
            }
        }
        return s.substring(l, l+res);
    }
}