题目描述

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

样例

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

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

算法分析

• 1、枚举数组中的每个位置i，从当前位置开始向两边扩散，
• 2、当回文子串是奇数时，从i开始往两边扩散，
• 3、当回文子串是偶数时，从i，i + 1开始往两边扩散
• 4、找到以i为中心的最长回文子串的长度，若存在回文子串比以前的长，则更新回文串的长度maxv，以及两端的位置l和r

时间复杂度 $O(n^2)$

Java 代码

class Solution {
    static int get_len(String s,int l,int r)
    {
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r))
        {
            l --;
            r ++;
        }
        return r - l - 1;
    }
    public String longestPalindrome(String iString) {
        if(iString.length() < 1) return "";
        int n = iString.length();

        int l = -1,r = n + 1;
        int maxv = 0;
        for(int i = 0;i < n;i ++)
        {
            //当回文子串是奇数时
            int len1 = get_len(iString,i,i);

            //当回文子串是偶数时
            int len2 = get_len(iString,i,i + 1);

            if(len1 > maxv)
            {
                maxv = len1;
                l = i - len1 / 2;
                r = i + len1 / 2;
            }
            if(len2 > maxv)
            {
                maxv = len2;
                l = i - (len2 - 1) / 2;
                r = i + len2 / 2;
            }
        }
        return iString.substring(l,r + 1);
    }

}