5. 最长回文子串(Longest Palindromic Substring)

来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/

描述

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

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

示例 2：
输入: “cbbd”
输出: “bb”

题解

中心扩展算法

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1, begin = 0;
        // 循环的右边界没有必要到len - 1，因为len - 1已经无法再向右扩展
        for (int i = 0; i < len - 1; i++) {
            int oddLen = expandAroundCenter(s, i, i);
            int evenLen = expandAroundCenter(s, i, i + 1);
            int curMaxLen = Math.max(oddLen, evenLen);
            if (curMaxLen > maxLen) {
                maxLen = curMaxLen;
                begin = i - (maxLen - 1) / 2;
            }
        }
        return s.substring(begin, begin + maxLen);
    }
    /**
     *
     * @param s 原始字符串
     * @param left 起始左边界
     * @param right 起始右边界
     * @return 回文串的长度
     */
    private int expandAroundCenter(String s, int left, int right) {
        int i = left, j = right, len = s.length();
        while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
        }
        // 退出循环时，左右两边的字符已不相等，回文的长度为(j - 1） - (i + 1) + 1 = j - i - 1
        return j - i - 1;
    }
}

复杂度分析

• 时间复杂度：
• 空间复杂度：