力扣：5-最长回文子串

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"
 

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

来源：力扣（LeetCode）

解题思路

首先我们要知道什么是回文子串，回文子串就是指正读和反读都一样的字符串。比如moom，level，civic等都是回文字符串。不难得出回文串分为两种，一种是围绕中间一个字符对称比如level，一种是围绕中间两个字符对称比如moom。所以我们的思路就是由中间向两边扩散，遍历到两边不一样时停止查询，返回这个回文串的长度。这个也叫中心扩展法。

需要注意的是要查询两种回文串的长度，容易遗漏两个字符为中心的回文串

这个用暴力做法的话会超时，一般这种题目用暴力是做不出来，所以我们就要观察，找规律，去优化。

这道题还有一个解法是利用动态规划，但是我对动态规划掌握的还不是特别熟练，所以这里就不用动态规划去做这道题，感兴趣的可以相关的题解

代码实现

class Solution {
public:
    string longestPalindrome(string s) {
            int res=s.size();
            int l,r;//用来记录最长回文串的左右边界
            int ans=0;//记录最长回文串的长度
            for(int i=0;i
            {
                int ans1=Find(s,i,i);//获得一个字符为中心的回文串长度
                int ans2=Find(s,i,i+1);//获得两个字符为中心的回文串长度
                //第一种更新回文串
                if(ans1>ans)
                {
                    l=i-(ans1-1)/2;
                    r=i+(ans1-1)/2;
                    ans=ans1;
                }
                //第二种更新回文串
                if(ans2>ans)
                {
                    l=i-(ans2-2)/2;
                    r=i-(ans2-2)/2;
                    ans=ans2;
                }
            }
            return s.substr(l,ans);//这里返回l开头，长度为ans的字符串
    }
    int Find(string s,int l,int r)
    {
        while(l>=0&&rsize()&&s[l]==s[r])
        {
            l--;
            r++;
        }
        return r-l-1;
    }
};