solution.md

# 最长回文子串

<p>给你一个字符串 <code>s</code>，找到 <code>s</code> 中最长的回文子串。</p><p> </p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>s = "babad"<strong><br />输出：</strong>"bab"<strong><br />解释：</strong>"aba" 同样是符合题意的答案。</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>s = "cbbd"<strong><br />输出：</strong>"bb"</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>s = "a"<strong><br />输出：</strong>"a"</pre><p><strong>示例 4：</strong></p><pre><strong>输入：</strong>s = "ac"<strong><br />输出：</strong>"a"</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>1 <= s.length <= 1000</code></li>	<li><code>s</code> 仅由数字和英文字母（大写和/或小写）组成</li></ul>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```

### after

```cpp
int main()
{
    Solution test;

    string ret;
    string s = "cbbd";
    ret = test.longestPalindrome(s);
    cout << ret << endl;
    return 0;
}
```

## 答案

```cpp
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(min(len1, len2), mlen);
            if (mlen > end - start + 1)
            {
                start = i - (mlen - 1) / 2;
                end = i + mlen / 2;
            }
        }
        return s.substr(start, mlen);
    }

private:
    int expendaroundcenter(string s, int left, int right)

    {
        int L = left;
        int R = right;
        while (L >= 0 && R < s.length() && s[R] == s[L])
        {
            L--;
            R++;
        }
        return R - L - 1;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    string longestPalindrome(string s)
    {
        int len = s.size();
        if (len == 0 || len == 1)
            return s;
        int start = 0;
        int max = 1;
        vector<vector<int>> dp(len, vector<int>(len));
        for (int i = 0; i < len; i++)
        {
            dp[i][i] = 1;
            if (i < len - 1 && s[i] == s[i + 1])
            {
                dp[i][i + 1] = 1;
                max = 2;
                start = i;
            }
        }
        for (int l = 3; l <= len; l++)
        {
            for (int i = 0; i + l - 1 < len; i++)
            {
                int j = l + i - 1;
                if (s[i] == s[j] && dp[i + 1][j - 1] == 1)
                {
                    dp[i][j] = 1;
                    start = i;
                    max = l;
                }
            }
        }
        return s.substr(start, max);
    }
};
```

### B

```cpp
class Solution
{
public:
    string longestPalindrome(string s)
    {
        if (s.length() == 1)
            return s;
        string rev = s;
        string res;
        std::reverse(rev.begin(), rev.end());
        if (rev == s)
            return s;
        int len = 0;
        for (int i = 0; i < s.length(); i++)
        {
            string temp;
            for (int j = i; j < s.length(); j++)
            {
                temp = temp + s[j];
                if (len >= temp.length())
                    continue;
                else if (rev.find(temp) != -1)
                {
                    string q = temp;
                    std::reverse(q.begin(), q.end());
                    if (q == temp)
                    {
                        len = temp.length();
                        res = temp;
                    }
                }
                else
                    break;
            }
            temp = "";
        }
        return res;
    }
};
```

### C

```cpp
class Solution
{
public:
    string longestPalindrome(string s)
    {
        string res = "";
        string temp = "";
        for (int i = 0; i < s.length(); i++)
        {
            for (int j = i; j < s.length(); j++)
            {
                temp = temp + s[j];
                string tem = temp;
                std::reverse(tem.begin(), tem.end());
                if (temp == tem)
                    res = res.length() > temp.length() ? res : temp;
            }
            temp = "";
        }
        return res;
    }
};
```