5. 最长回文子串

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

示例 1：

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

输入: "cbbd"
输出: "bb"

image.png

class Solution {
    
    
    /*  * 分析：通过分析子串的特性
               回文为奇数时  aba  中位数两边的数（距离中位数大小一样的时候）相等
             * 回文为偶数时 aabb 中位数旁边（距离中位数相等的）相等
             * 
             */
    public String longestPalindrome(String s) {
        if (s.length()==0)
            return s;
        int max = 1,mid = 0; //回文最短是1（0）
        int i , j ,k = 0;
        //回文串位 偶数
        for(k = 0;k<s.length();k++) {
            i = k;
            j = k+1;
            while(i>=0 && j<s.length() && isEqualNumberOfString(i,j,s)) {
                i--;
                j++;
            }
            // 注意最后 多做了一次循环
            int len = j - i + 1 -2 ;
            if(len > max) {
                max = len;
                mid = k;
            }
            
        }
        
        //回文为偶数
        for(k = 1;k<s.length();k++) {
            i = k-1;
            j = k+1;
            while(i>=0 && j<s.length() && isEqualNumberOfString(i, j, s)) {
                i--;
                j++;
            }
            // 注意最后 多做了一次循环
            int len = j-i +1 -2 ;
            if(len > max) {
                max = len;
                mid = k;
            }
        }
        /*
         * beginIndex -- 起始索引（包括）。
            endIndex -- 结束索引（不包括）。  
         */
        if(max % 2==0)
            return s.substring(mid  - max/2 +1 , mid + max/2 + 1); 
        else
            return s.substring(mid - max/2 ,mid +max/2 +1);
        
    }
    
    
    public static boolean isEqualNumberOfString(int i ,int j,String s) {
        if(s.charAt(i) == s.charAt(j))
            return true;
        else
            return false;
    }
    
    
}