leetcode5. 最长回文子串

分析

dp

class Solution {
public:
    vector<vector<int>>f;
    string longestPalindrome(string s) {
        int n=s.size();
        f.assign(n,vector<int>(n,true));
        int start=0,count=1;
        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                f[i][j]=f[i+1][j-1]&&(s[i]==s[j]);
                if(f[i][j]&&count<j-i+1){
                    count=j-i+1;
                    start=i;
                }
            }
        }
        return s.substr(start,count);
    }
};

中心扩散法

要么从i位置开始扩展，要么从i和i+1的位置开始扩展，将回文串的所在区间存入Pair中，最后取最大的区间值即可。

class Solution {
public:
    pair<int,int> midu(string s,int left,int right){
        while(left>=0&&right<s.size()&&s[left]==s[right])left--,right++;
        return {left+1,right-1};
    }
    string longestPalindrome(string s) {
        int start=0,end=0;
        for(int i=0;i<s.size();i++){
            auto[l1,r1] =midu(s,i,i);
            auto[l2,r2]=midu(s,i,i+1);
            if(r1-l1>end-start)
                start=l1,end=r1;
            if(r2-l2>end-start)
                start=l2,end=r2;
        }
        return s.substr(start,end-start+1);
    }
    
};