题目链接

5. 最长回文子串

思路1：中心扩散法

遍历字符串 s，对于每个字符都以它为中心向两边扩散，测得最长回文子串。

注意：在扩散的过程中要分回文串长度奇偶进行扩散，因为长度为偶数的回文串中心是两个字母

时间复杂度：\(O(n^2)\)

空间复杂度：\(O(1)\)

代码1

class Solution {
    public String longestPalindrome(String s) {
        int[] result = new int[2];

        for(int i = 0; i < s.length() - 1; i++){
            int[] temp = spread(s, i, i);
            if((result[1] - result[0] + 1) < (temp[1] - temp[0] + 1)){
                result = temp;
            }

            temp = spread(s, i, i + 1);
            if((result[1] - result[0] + 1) < (temp[1] - temp[0] + 1)){
                result = temp;
            }
        }

        return s.substring(result[0], result[1] + 1);
    }

    int[] spread(String s, int left, int right){
        while(left >= 0 && right < s.length()){
            if(s.charAt(left) != s.charAt(right)){
                break;
            }
            left--;
            right++;
        }

        if(left < 0 || right == s.length()){
            left++;
            right--;
        }

        return s.charAt(left) == s.charAt(right) ? new int[]{left, right} : new int[]{left + 1, right - 1};
    }
}

思路2：Manacher 算法