题目描述

给定一个字符串，返回它的最长回文子串。如果存在多个答案，返回任意一个即可。字符串长度 ≤≤ 1000。

样例

样例1
输入：”babad”
输出：”bab”
注意：”aba” 也是一个合法的答案.
样例2
输入：”cbbd”
输出：”bb”

(暴力枚举) $O(n^2)$

步骤：

• 枚举对称点 s[i]
• 以对称点向两边扩散维护一个回文子串的区间 注意区间的合法性

C++ 代码

class Solution {
public:
    int len = 0;
    int idx = -1;

    void update(int l, int r)
    {
        if(r - l + 1 > len)
            len = r - l + 1,idx = l;
    }

    string longestPalindrome(string s) {
        // 枚举对称点
         for(int i = 0; i < s.size(); i++)
        {
            int j, k; // 区间左右端点
            // 奇回文
            for(j = i, k = i; j >= 0 && k < s.size(); j--, k++)
                if(s[j] == s[k]) update(j, k);
                else break;
            // 偶回文    
            for(j = i, k = i + 1; j >= 0 && k < s.size(); j-- , k++ )
                if(s[j] == s[k]) update(j, k);
                else break;
        }

        return s.substr(idx, len);
    }
};