题解 | #最长公共子序列(二)#

class Solution {
public:
   string LCS(string s1, string s2) {
        s1=" "+s1,s2=" "+s2;
        vector<pair<int,string>>dpnow(s2.length(),{0,""});
        vector<pair<int,string>>dppre(s2.length(),{0,""});
        bool fl=true;
        for(int i=1;i<s1.length();i++)
        {
            for(int j=1;j<s2.length();j++)
             {
                if(fl)
                {
                    if(s1[i]==s2[j])dpnow[j].first=dppre[j-1].first+1,dpnow[j].second=dppre[j-1].second+s1[i];
                    else dpnow[j]=dppre[j].first>dpnow[j-1].first?dppre[j]:dpnow[j-1];
                }
                else
                {
                    if(s1[i]==s2[j])dppre[j].first=dpnow[j-1].first+1,dppre[j].second=dpnow[j-1].second+s1[i];
                    else dppre[j]=dpnow[j].first>dppre[j-1].first?dpnow[j]:dppre[j-1];
                }
             }
             fl=!fl;
        }
        if(!fl)return dpnow[s2.length()-1].second.length()==0?"-1":dpnow[s2.length()-1].second;
        return dppre[s2.length()-1].second.length()==0?"-1":dppre[s2.length()-1].second;
    }
};