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

class Solution {
public:
    /*
     增加path记录dp选择时的路径，最后按图索骥就能找到这个序列
     */
    string LCS(string s1, string s2) {
        vector<vector<int>>d(s1.size()+1,vector<int>(s2.size()+1,0));
        vector<vector<int>>path(s1.size()+1,vector<int>(s2.size()+1,0));

        for(int i=1;i<=s1.size();++i)
        {
            for(int j=1;j<=s2.size();++j)
            {
                if(s1[i-1]==s2[j-1])
                {
                    d[i][j]=d[i-1][j-1]+1;
                    path[i][j]=1;
                }
                
                else
                {
                    if(d[i-1][j]>d[i][j-1])//来自上方
                    {
                        d[i][j]=d[i-1][j];
                        path[i][j]=2;
                    }
                    else 
                    {
                        //来自左方，相等也包含在内
                        d[i][j]=d[i][j-1];
                        path[i][j]=3;
                    }
                }
            }
        }


        int i=s1.size(),j=s2.size();
        string res="";
        //从后往前，前插逆序
        while(i>0 && j>0)
        {
            if(path[i][j]==1)
            {
                res=s1[i-1]+res;
                i--;
                j--;
            }
            else if(path[i][j]==2)i--;
            else if(path[i][j]==3)j--;
        }
        if(res=="")return "-1";
        else return res;
    }
};