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

public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        vector<vector<int>> dp(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]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        if (dp[s1.size()][s2.size()] == 0) return "-1";
        int m = s1.size();
        int n = s2.size();
        string res;
        for(int i=m,j=n; dp[i][j]>=1;){
            if (s1[i-1] == s2[j-1]){
                res += s1[i-1];
                i--;
                j--;
            } else if(dp[i-1][j] >= dp[i][j-1]) {
                i--;
            } else{
                j--;
            }
        }
        reverse(res.begin(), res.end());
        return res;
        
        
         // write code here
    }
};