最长回文子串

5. 最长回文子串

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

中心扩散法

class Solution {
    public String longestPalindrome(String s) {
        int len = 1;
        String res = "";
        for(int i = 0; i < s.length(); i++){
            String s0;
            String s1 = extend(s,i,i+1);
            String s2 = extend(s,i,i);
            if(s1.length() > s2.length()){
                s0 = s1;
            }else{
                s0 = s2;
            }
            if(s0.length() > res.length()){
                res = s0;
            }

        }
        return res;
    }

    public String extend(String s, int i, int j){
        while(i >= 0 && j <= s.length()-1 && s.charAt(i) == s.charAt(j)){
            i--;
            j++;
        }
        return s.substring(i+1,j);
    }
}

动态规划

同上一题

class Solution {
    public String longestPalindrome(String s) {
        
      char[] chars = s.toCharArray();
        int len = chars.length;
        boolean[][] dp = new boolean[len][len]; //dp[i][j]表示[i,j]是否为回文子串
        int max_len = 0;
        String res = "";
        for(int i = len-1 ; i >= 0; i--){
            for(int j = i ; j < len; j ++){
                if(chars[i] == chars[j]){
                    if(j - i <= 1){ //长度为1的或2的且相同一定是回文子串，如a，aa
                        dp[i][j] = true;
                    }else{
                        if(dp[i+1][j-1]){
                            dp[i][j] = true;
                        }
                    }
                    if(dp[i][j] && j - i + 1 > max_len){
                        max_len = j - i + 1;
                        res = s.substring(i, j+1);
                    }
                }
                
            }
        }
        return res;
    }
}