[0005] 最长回文子串

题目描述

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

示例 1：

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

示例 2：

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

题目解析

本题是一个暴力枚举题，可以从左到右枚举回文串的中心位置，然后向两边展开查找最长的两端点。

不确定性

空字符串

字符串中包含哪些字符

子串的定义是什么？比如xax，xx算它的子串吗？一般子串是字符中连续的一断，非连续的叫子序列。

方法一：[暴力枚举法]

分析

由于题目中给出的数据范围比较小，$O(n^2)$算法可以通过此题。

思路

可以先枚举回文串的中心位置，然后用贪心法往两边一直找相等的字符。

注意

空字符串特殊判断，回文串分为奇数长度和偶数长度进行处理。

知识点

暴力法。 Manacher（马拉车算法）

复杂度

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

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

代码

class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.size();
        if(len==0||len==1)//考虑空字符串
            return s;
        int start=0;//记录回文子串起始位置
        int end=0;//记录回文子串终止位置
        int mlen=0;//记录最大回文子串的长度
        for(int i=0;i<len;i++)
        {
            int len1=expendAroundCenter(s,i,i);//一个元素为中心，长度为奇数
            int len2=expendAroundCenter(s,i,i+1);//两个元素为中心，长度为偶数
            mlen=max(max(len1,len2),mlen);
            if(mlen>end-start+1)
            {
                start=i-(mlen-1)/2;
                end=i+mlen/2;
            }
        }
        return s.substr(start,mlen);
        //该函数的意思是获取从start开始长度为mlen长度的字符串
    }
private:
    int expendAroundCenter(string s,int left,int right)
    //计算以left和right为中心的回文串长度
    {
        int L=left;
        int R=right;
        while(L>=0 && R<s.length() && s[R]==s[L])
        {
            L--;
            R++;
        }
        return R-L-1;
    }
};