Java最大回文子串leetcode

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

提示：

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

1、暴力解法

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() == 1){
            return s;
        }

        char[] chs = s.toCharArray();
        int MaxLen = 1;
        int begin = 0;
        //枚举长度大于一的字串
        for(int i = 0;i < s.length()-1;i++){
            for(int j = i + 1;j < s.length();j++){
                //子串长度j-i+1
                if(j - i + 1 > MaxLen && isPalindrome(chs,i,j)){
                    MaxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+MaxLen);
    }

    public boolean isPalindrome(char[] chs,int i,int j){
        while(i < j){
            if(chs[i] != chs[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

执行用时：149 ms, 在所有 Java 提交中击败了46.34%的用户

内存消耗：41.4 MB, 在所有 Java 提交中击败了70.37%的用户

2、动态规划

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() == 1){
            return s;
        }

        char[] chs = s.toCharArray();
        int MaxLen = 1;
        int begin = 0;
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        for(int i = 0 ;i < n;i++){
            dp[i][i] = true;
        }
        for(int j = 1;j < n;j++){
            for(int i = 0;i < j;i++){
                if(chs[i] != chs[j]){
                    dp[i][j] = false;
                }else{
                    //子串长度小于等于3
                    if(j-i < 3){
                        dp[i][j] = true;
                    }else{
                        //dp[i+1][j-1]已经存在
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                if(dp[i][j] && j-i+1 > MaxLen){
                    MaxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+MaxLen); 
    }
}

执行用时：124 ms, 在所有 Java 提交中击败了51.71%的用户

内存消耗：44.6 MB, 在所有 Java 提交中击败了30.29%的用户

3、中心扩散

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() == 1){
            return s;
        }

        int maxLen = 0;
        //数组第一位记录起始位置，第二位记录长度
        int[] res = new int[2];
        for (int i = 0; i < s.length() - 1; i++) {
            int[] odd = centerSpread(s, i, i);
            int[] even = centerSpread(s, i, i + 1);
            int[] max = odd[1] > even[1] ? odd : even;
            if (max[1] > maxLen) {
                res = max;
                maxLen = max[1];
            }
        }
        return s.substring(res[0], res[0] + res[1]);
    }

    private int[] centerSpread(String s, int left, int right) {
        int len = s.length();
        while (left >= 0 && right < len) {
            if (s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            } else {
                break;
            }
        }
        return new int[]{left + 1, right - left - 1};
    }
}