题目

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

例1：

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

例2

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

提示

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

代码

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);
    }
};

思路

在做的几组测试中，尝试过几种方法，均可实现。一是直接使用二分查找对比，此处注意区分字符串长度的奇偶情况，分开讨论；二是将字符串s先反转，再复制为一个新的字符串new_s，再进行对比两个字符串二分之一长度的字符是否相同，同样需要区分字符串长度的奇偶情况。