JAVA版《最长回文子串》小白易懂版

暴力解法

直接判断每一个子串是不是回文子串，然后取其中最长的值返回

public class Palindrome {
    public int getLongestPalindrome(String A, int n) {
        int maxLen = 0;
        //暴力解法
        for(int i = 0; i < n; i++){
            for(int j = i+1; j <= n; j++){
                String now = A.substring(i,j);
                if(isPalindrome(now) && now.length() > maxLen){
                    maxLen = now.length();
                }
            }
        }
        return maxLen;
    }

    //判断子串是不是回文子串
    public boolean isPalindrome(String s){
        int l = s.length();
        for(int i = 0; i < l/2; i++){
            if(s.charAt(i) != s.charAt(l-i-1))
                return false;
        }
        return true;
    }
}

中心扩散法

public class Palindrome {
    public int getLongestPalindrome(String A, int n) {
        if(n == 0)
            return 0;
        int maxLen = 1;
        //中心枚举到n-2位置
        for(int i = 0; i < n-1; i++){
            // 比较以i为中心扩散的回文子串 && 以i和i+1为中心扩散的回文子串 哪个大取哪个
            int len = centerSpread(A,i,i) > centerSpread(A,i,i+1)? centerSpread(A,i,i):centerSpread(A,i,i+1);
            maxLen = Math.max(maxLen,len);   
        }
        return maxLen;
    }

    //若left==right 则扩散中点为一个，此时的回文子串为奇数
    //若left!=right，则扩散的中点为 left和right，此时的回文子串为偶数
    public int centerSpread(String s, int left, int right){
        int len = s.length();
        int l = left;
        int r = right;
        while(l >= 0 && r <= len-1){
            //若相等则继续扩散
            if(s.charAt(l) == s.charAt(r)){
                l--;
                r++;
            }else{
                break;
            }
        }
        //为什么还要减2  因为上面while循环终止了，此时s.charAt(l) != s.charAt(r)
        //所以此时的回文子串的左右边界其实是  l-1，  r-1
        return r-l+1-2;
    }
}