BM65最长公共子序列二

描述

给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回”-1”。目前给出的数据，仅仅会存在一个最长的公共子序列

数据范围：0 <= |str1|,|str2| <= 20000

要求：空间复杂度 O(n^2)，时间复杂度 O(n^2)

示例

输入："1A2C3D4B56","B1D23A456A"
返回值："123456"

思路

普通的最长公共子序列只需要返回长度，这道题需要返回子序列，而且受空间复杂度限制不能开二维string数组记录。

需要用dp的结果倒推出子序列。

代码

string LCS(string s1, string s2) {
    // write code here
    int l1 = s1.length();
    int l2 = s2.length();
    s1 = "+"+s1;
    s2 = "-"+s2;
    int dp[l1+1][l2+1];
    memset(dp, 0, sizeof(dp));
    for(int i=1;i<=l1;i++){
        for(int j=1;j<=l2;j++){
            if(s1[i]==s2[j]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    string ans;
    for(int i=l1,j=l2;dp[i][j]>=1;){
        if(s1[i]==s2[j]){
            ans = s1[i]+ans;
            i--;
            j--;
        }else{
            if(dp[i-1][j]>dp[i][j-1]) i--;
            else j--;
        }
    }
    if(ans.length()==0) ans = "-1";
    return ans;
}