LeetCode刷题之旅（5）--最长回文子串（中等题）

方法一耗时很长但是思路容易理解，还要接着想其他更好的方法呀，加油。

题目:最长回文子串

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

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

示例2:
输入: "cbbd"
输出: "bb"

解题思路：

方法一：

从头到尾遍历字符串s，当前后有字母相同时，证明有可能这两个字母间的串为最长回文串，所以，判断该串是否是回文串即可，若是则输出成新串new_s即可。
而判断是否是回文串也很简单，一样的思路，如果遍历字符串，如果一直头尾相等，那么该串就是回文串了。

class Solution {
public:
    string longestPalindrome(string s) {
        int m,n,max_length=0,m1,n1;
        string new_s="";
        for(m=0,n=s.size()-1;m<s.size();n--)
        {
            if(s[m]==s[n])
            {
                if(is_huiwenstring(s,m+1,n-1))
                {
                    if(n-m+1>max_length)
                    {
                        max_length=n-m+1;
                        new_s="";
                        for(m1=m,n1=n;m1<=n1;m1++)
                        {
                            new_s=new_s+s[m1];
                        }
                    }
                }
            }
           if(m==n)
           {
               m++;
               n=s.size();
           }
        }
        
        return new_s;
    }
    
    bool is_huiwenstring(string s,int A,int B)
    {
        int i=0,j=0;
        if((B-A+1)%2==0)
        {
            for(i=A,j=B;i<(B+A+1)/2;i++,j--)
            {
                if(s[i]!=s[j])
                {
                    return false;
                }
            }
            
        }
        else
        {
            for(i=A,j=B;i<(B+A)/2;i++,j--)
            {
                if(s[i]!=s[j])
                {
                    return false;
                }
            }
        }
        return true;
    }
};
执行用时：1328 ms

方法二：

这个方法就是找到最长子串的中心，然后想外部扩展，使用了i、j的双游标。

static const auto __ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    string longestPalindrome(string s) {
        int center=0,left=0,right=0,max_length=0,place=0;
        while(center<s.size())
        {
            left=center;
            right=center;
            while(right<s.size()&&s[right]==s[right+1])//右边的游标先从中心出发，这样就可以保证，无论回文子串是偶数长度还是奇数长度，left和right都可以分开。简单来说，因为在偶数的情况下，中心的两个字符必然相等，该操作等同于产生了左右两个中心，一个是原地不动的left_center，一个是r++了以后的right_center
            {
                right++;
            }
            center=right+1;//更新中心的位置
            while(left>=0&&right<s.size()&&s[left]==s[right])
            {
                left--;
                right++;
            }
            if(max_length<right-left+1-2)
            {
                max_length=right-left+1-2;
                place=left+1;
            }
            
        }
        return s.substr(place,max_length);
       
    }
};

执行用时：4 ms