题解 | #最长回文子串# 中点扩散 + 剪枝

import java.util.*;


public class Solution {
    int findMax(char[] arr, int sidx, int eidx){
        int len = arr.length;
        int count = 0;
        while(sidx-count >= 0 && eidx + count < len && arr[sidx-count] == arr[eidx + count]){
            count++;
        }
        return 2 * (count - 1);
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
    public int getLongestPalindrome (String str) {
        // write code here
        int len = str.length();
        int max = 0;
        // 单个满足回文
        char[] arr = str.toCharArray();
        for(int i=0;i<len-1;i++){
            max = Math.max(max,findMax(arr,i,i) + 1);
            max = Math.max(max,findMax(arr,i,i+1) + 2);
            if(max/2 >= len - i){
                break;
            }
        }
        max = Math.max(max,findMax(arr,len-1,len-1) + 1);
        return max;
    }
}

如何剪枝

进行中点扩散时，如果到终点的距离，不到已经获取到的最长回文子串长度的一半，那么即使剩余的全是回文子串，则最后长度也小于目前获得的值。

为什么用右侧作为判断终点

对于一个可能的回文子串，能够获取的最大长度就是在中间点位置进行扩散，长度可能等于整个字符串的长度，过了这个点之后，不会再取得更大预期值了