题解 | #最长回文子串#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    public int fun(String a,int begin,int end){
        //定义一个函数fun可根据字符串a从任意两点(若奇数展开则两点都为i,偶数展开两点为i和i+1)向两边展开并求得相同子串的长度
        while(begin>=0&&end<=a.length()-1&&a.charAt(begin)==a.charAt(end)){
            begin=begin-1;end=end+1;
        }
        return end-begin+1-2;
        //end-begin+1是从索引begin到索引end的子串长度,由于while循环结束时begin额外减了1,end额外加了1,所以实际长度要再减去2
    }
    public int getLongestPalindrome (String A) {
        // write code here
        int maxlen=1;//初始最大回文子串为1
        for(int i=0;i<A.length()-1;i++)//遍历A,从索引i处向两边展开,由于每一个索引处必须考虑奇数(begin=i,end=i)和偶数(begin=i,end=i+1)两种展开方式并取最大值,所以索引最多遍历到A.length()-2处,也就是倒数第二个字符
        maxlen=Math.max(maxlen,Math.max(fun(A,i,i),fun(A,i,i+1)));
        //这里用到递归思想,maxlen一定是取这次遍历和上次遍历中的最大值,然后这次遍历又分为奇数(begin=i,end=i)和偶数(begin=i,end=i+1)两种展开方式,取其中的最大值
        return maxlen;
    }
}