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

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