5. 最长回文子串

题目来源：https://leetcode-cn.com/problems/longest-palindromic-substring/

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

示例 1：

输入: “babad”

输出:”bab”

注意:”aba” 也是一个有效答案。

示例 2：

输入: “cbbd”

输出: “bb”

解法

C++代码：

解法一：暴力破解法（菜 鸡 必 会 法）||（ LeetCode 不 能 A C）

class Solution {
public:
    string longestPalindrome(string s) {
        int start=0,end=0;
        for(int i=0;i<s.length();i++)
        {
            for(int j=i;j<s.length();j++)
            {
                string t=s.substr(i,j-i+1);
                if(ifPalindromic(t))
                {
                    if(j-i>end-start)
                    {
                        start=i;end=j;
                    }
                }
            }
        }
        string ret=s.substr(start,end-start+1);
        return ret;
    }
    bool ifPalindromic(string s){ //判断是否是回文
        for(int i=0;i<s.length()/2;i++)
            if(s[i] != s[s.length()-1-i])
                return false;
        return true;
    }
};

复杂度分析：

时间复杂度：O(n3)

空间复杂度：O(1)

解法二：中心扩散算法

暴力破解在很多场合往往是最容易想到的方法，但是通常在复杂度方面表现很差，效率很低下。

本题最容易想到的就是中心扩散算法。

中心扩散算法顾名思义就是从中心往两边逐步判断，但存在以下两种情况：

case 1： 中间值与左侧或者右侧任一侧相同，需要将相同一侧的指针往同方向移动

case 2： 中间值与两侧值都不相同，直接比较两侧值是否相同即可

下举例说明中心扩散算法：

      left↓start↓right      
e c b a a b d

Step 1： 首先left指针左移一位。

    left↓ start↓right      
e c b a a b d

判断 start==left？是则left继续左移一位，否则保持不变。

    left↓ start↓right      
e c b a a b d

Step 2： right指针右移一位。

    left↓ start ↓right    
e c b a a b d

判断 start==right？是则right继续右移一位，否则保持不变。

    left↓ start   ↓right  
e c b a a b d

Step 3： 判断right==left？是则left–，right++；否则跳出循环。

  left↓   start     ↓right
e c b a a b d

此时left!=right,所以返回（left+1，right-1）

因此该轮次得到的回文子串为baab.

实现：

class Solution {
public:
    string longestPalindrome(string s) {
        int left,right;
        int start=0,len,maxlen=1;
        for(int i=0;i<s.length();i++)
        {
            left=i-1;
            right=i+1;
            len=1;
            while(left>=0&&s[i]==s[left])
            {
                left--;
                len++;
            }
            while(right<s.length()&&s[i]==s[right])
            {
                right++;
                len++;
            }
            while(left>=0&&right<s.length()&&s[left]==s[right])
            {
                left--;
                right++;
                len+=2;
            }
            if(len>maxlen)
            {
                start=left+1;
                maxlen=len;
            }
        }
        string t=s.substr(start,maxlen);
        return t;
    }
};

执行用时 :108 ms, 在所有 C++ 提交中击败了57.47%的用户

内存消耗 :6.6 MB, 在所有 C++ 提交中击败了100.00%的用户

复杂度分析：

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

空间复杂度：O(1)