最长回文子串

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 = s.length();
        if(len < 2){
            return s;
        }
        int max_len = 1;
        int start = 0; //最长回文子串的起始下标
        String max_str = "";
        char[] charArray = s.toCharArray();
        for(int i = 0; i < len - 1; i++){
            for(int j = i + 1; j < len; j++){
                if(j - i + 1 > max_len && isPalindromic(charArray, i, j)){
                    start = i;
                    max_len = j - i + 1;
                }
            }
        }
        return s.substring(start, start + max_len);
    }

    public boolean isPalindromic(char[] s, int left, int right){
        while(left < right){
            if(s[left] != s[right]){
                return false;
            }
            left ++;
            right --;
        }
        return true;
    }
}

中心扩散法

class Solution {
   
    //中心扩散法
    public String longestPalindrome(String s) {
        int left = 0 , right = 0;
        int len = 1; //当前子串长度
        int max_len = 0;
        String max_str = "";
        for(int i = 0; i < s.length(); i++){
            left = i - 1;
            right = i + 1;
            //左扩散
            while(left >= 0 && s.charAt(left) == s.charAt(i)){
                left --;
                len ++;
            }
            //右扩散
            while(right < s.length() && s.charAt(right) == s.charAt(i)){
                right ++;
                len ++;
            }
            //左右扩散
            while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
                left --;
                right ++;
                len += 2;
            }
            if(len > max_len){
                max_len = len;
                max_str = s.substring(left + 1, right);
            }
            len = 1;
        }
        
         return max_str;
    }

}

动态规划

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;
    }
}