leetcode最长回文子串

题目来源

解题方法

动态规划

dp[i,j]其中i，j表示子串的首尾，一个长度的子串一定是回文的，两个长度的且相等字母的子串也一定是回问的，于是dp[i][i]=1,dp[i][i+1]=1

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n==0 || n==1)
            return s;
        int start=0;//记录子串的起始位置
        int max=1;//记录子串最大长度
        vector<vector<int>> dp(n, vector<int>(n));
        for(int i=0;i<n;i++){
            dp[i][i]=1;
            if(i+1<n && s[i] == s[i+1]){
                dp[i][i+1]=1;
                max=2;
                start=i;
            }
        }
        for(int l=3;l<=n;l++){ // l是要处理的子串长度，从3开始
            for(int i=0;i+l-1<n;i++){
                int j = i+l-1;// 终止位置
                if(s[i]==s[j]&&dp[i+1][j-1]){
                    dp[i][j]=1;
                    max=l;
                    start=i;
                }
            }
        }
        return s.substr(start, max);
    }
};

中心展开法

对于每个字符，可以以单个字符展开，若与后一个字符相等，也可以将其和后面一个字符展开，判断最大的长度

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n==0 || n==1)
            return s;
        int start=0;//记录子串的起始位置
        int end=0; //记录子串的结束位置
        int mLen=1;//记录子串最大长度
        for(int i=0;i<n;i++){
            int len1=helper(s,i,i);// 以一个点为中心展开
            int len2=helper(s,i,i+1);// 以两个点为中心展开
            mLen=max(max(len1,len2),mLen);
            if(mLen > end-start+1){
                start=i-(mLen-1)/2;
                end=i+mLen/2;
            }
        }
        cout << mLen;
        return s.substr(start, mLen);
    }
    int helper(string s, int left, int right){
        int L=left;
        int R=right;
        while(L>=0 && R<s.size() && s[L]==s[R]){
            L--;
            R++;
        }
        return R-L-1;
    }
};