最长回文子串

最长回文子串

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

示例 1：

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

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

解题思路：遍历字符串，将每一个字符都当作回文的中点来计算当该点为中点时的回文子串长度并记录此时的回文的起点和终点

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.isEmpty())
            return s;
        
        char ch[] = s.toCharArray();
        int l = 0, r = 0;
        for(int i = 0; i < ch.length; i++) {
            int len1 = getLen(ch, i, i);
            int len2 = getLen(ch, i, i + 1);
            int len = Math.max(len1, len2);
            if(len > r - l + 1) {
                //当回文长度是奇数时
                if(len % 2 != 0) {
                    l = i - len / 2;
                    r = i + len / 2;
                } else {
                    //当回文长度是偶数时
                    //长度len为偶数时的i和长度为len-1时的i是相等的
                    l = i - (len - 1) / 2;  
                    r = i + len / 2;
                }
            }
        }
        
        return s.substring(l, r + 1);
    }
    
    private int getLen(char[] ch, int l, int r) {
        while(l >= 0 && r < ch.length && ch[l] == ch[r]) {
            l--;
            r++;
        }
        
        return r - l - 1;
    }
}