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

#include <vector>
class Solution {
public:
    //最长是多少？怎么得到那个序列？
    string LCS(string s1, string s2) {
        if( s1.size() ==0 || s2.size()==0 ){
            return "-1";
        }

        vector< vector<int> > dp(s1.size()+1, vector<int>( s2.size()+1, 0 ));
        //dp[i][j]表示：截至s1[i]和s2[j] 目前最长的子序列长度；
        //如果相等s1[i-1]==s2[j-1],dp[i][j] = dp[i-1][j-1] + 1;

        vector< vector<int> > direc(dp);  
        //记录转变，1表示从左上角得来，回头构建时需要字符加入答案子串；2表示从从左边而来，3表示上面

        for(int i=1; i<=s1.size(); i++){
            for(int j=1; j<=s2.size(); j++){
                if(s1[i-1] == s2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    direc[i][j] = 1;
                }else{
                    dp[i][j] = max( dp[i-1][j], dp[i][j-1] );

                    if(dp[i][j] == dp[i-1][j]){
                        direc[i][j] = 3;
                    }else{
                        direc[i][j] = 2;
                    }
                }
            }
        }


        int maxlen = dp.back().back();
        int row = s1.size();
        int col = s2.size();
        string ans="";
        while(row >= 1 && col >= 1){  //只有相等时，就是公共子序列的一员
            if(direc[row][col] == 1){
                ans = s1[row-1] + ans;
                row--;
                col--;
            }else if(direc[row][col] == 2){
                col--;
            }else if(direc[row][col] == 3){
                row--;
            }
        }

        return ans == "" ? "-1": ans;
    }
};