首先使用暴力破解方法求解:

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n < 2) return s;
        int maxlen = 1,begin = 0;
        for(int i = 0;i < n - 1;i++)
        {
            for(int j = i + 1;j < n;j++)
            {
                if(j - i + 1 > maxlen && isvalidPalindome(s,i,j))
                {
                    begin = i;
                    maxlen = j -i + 1;
                }
            }
        }
        
        return s.substr(begin,maxlen);
    }
private:
    bool isvalidPalindome(string s,int i,int j){
        while(i < j)
        {
            if(s[i++] != s[j--]) return false;
        }
        
        return true;
    }
};

这里首先判断了字符串s长度,如果小于2直接返回s,默认begin为0,长度为1,如果字符串没有长度大于1的回文串就返回第一个字符,暴力破解存在超时,无法全部AC.

47 / 176 test cases passed.
Status: Time Limit Exceeded
Submitted: 0 minutes ago
Last executed input:
"ibvjkmpyzsifuxcabqqpahjdeuzaybqsrsmbfplxycsafogotliyvhxjtkrbzqxlyfwujzhkdafhebvsdhkkdbhlhmaoxmbkqiwius……"

动态规划

使用动态规划算法,递推方程dp[i][j]表示字符串s的第i个字符到第j个字符组成的字符串是否是回文串。
dp[i][j]=dp[i+1][j-1] ^(s[i] == s[j])
递推的起始条件是:
子串长度小于等于2
dp[i][i] = 1
dp[i][j] = 1 (if(s[i] == s[j])

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        string ans;
        for(int step = 0; step < n;step++)
        {
            for(int i = 0;i + step < n;i++)
            {
                int j = i + step;
                if(step == 0)
                    dp[i][j] = 1;
                else if(step == 1)
                    dp[i][j] = (s[i] == s[j]);
                else
                {
                    dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1];
                }
                
                if(dp[i][j] && (j - i + 1 > ans.size()))
                    ans = s.substr(i,j-i+1);
            }
        }
        
        return ans;
    }
};