给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2:

输入: “cbbd”
输出: “bb”

思路

遍历字符串,对于某个子串,如果其左右两边的字符依然相等,就继续遍历,得到最长的长度,最后
截取子串即可

思路不难,最重要的是判定清楚边界条件,下面的代码就有三个地方要弄清楚,这也是我将这个题记录下来的原因

class Solution {
    public String longestPalindrome(String s) {
        if(s.length()==0)return "";
        int start=0;
        int end=0;
        char[] ch=s.toCharArray();
        for(int i=0;i<ch.length;i++){
            //两种回文,一是一个中心,二是两个中心
            int len1=huiwen(ch,i,i);
            int len2=huiwen(ch,i,i+1);
            int len=Math.max(len1,len2);
            if(len>end-start){
                //因为对于huiwen(ch,i,i+1)
                //长度是从i开始左右计算的,所以i左边的数比右边的少一个
                //在往左寻开始坐标的时候先减一
                 start=i-(len-1)/2;
                 end=i+len/2;
            }
        }
        //end是闭区间的右边,substring 中终点是不纳入的
        return s.substring(start,end+1);
    }
    public int huiwen(char[] s,int l,int r){
        if(l>r)return 0;
        while((l>=0&&r<s.length)&&s[l]==s[r]){
            l--;
            r++;
        }
        //返回区间长度然后由于左右都加了1所以减掉2,得到回文长度
        return (r-l+1)-2;
    }
}