BM65. [最长公共子序列(二)]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM65. 最长公共子序列(二)

https://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11?tpId=295&sfm=discuss&channel=nowcoder

题目的主要信息：

• 仅存在一个最长公共子序列，不需要去重
• 最长公共子序列为空需要返回"-1"，而不是空序列，最后要变换

我们以dp[i][j]表示在s1中以i结尾，s2中以j结尾的字符串的最长公共子序列长度，若是i与j相等，则该问题可以变成1+dp[i][j]，即最长公共子序列长度加1，若是不相等，则换成两个子问题：dp[i][j-1]或者dp[i-1][j]，由此用递归即可以解决。
但是递归的复杂度过高，重复计算了太多部分，因此可以用动态规划，从前往后加：

方法一：动态规划
具体做法：
可以用二维矩阵dp记录在s1中以i结尾，s2中以j结尾的字符串的最长公共子序列长度，由此形成一个表，表从1开始往后相加。因最后要返回该序列，所以在构造表的同时要以另一个二维矩阵记录打印方向。

class Solution {
public:
    string x = "";
    string y = "";
    string ans(int i, int j, vector<vector<int>>& b){
        string res = "";
        if(i == 0 || j == 0)///递归终止条件
            return res;
        if(b[i][j] == 1)
        {
            res += ans(i - 1, j - 1, b);
            res += x[i - 1];
        }
        else if(b[i][j] == 2)
        {
            res += ans(i - 1, j, b);
        }
        else if(b[i][j] == 3)
        {
            res += ans(i,j - 1, b);
        }
        return res;
    }
    string LCS(string s1, string s2) {
        if(s1.length() == 0 || s2.length() == 0)
            return "-1";
        int len1 = s1.length();
        int len2 = s2.length();
        x = s1;
        y = s2;
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        vector<vector<int>> b(len1 + 1, vector<int>(len2 + 1, 0));
        for(int i = 1; i <= len1; i++)
        {
            for(int j = 1; j <= len2; j++)
            {
                if(s1[i - 1] == s2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    b[i][j] = 1;///来自于左上方
                }
                else
                {
                    if(dp[i - 1][j] > dp[i][j - 1])
                    {
                        dp[i][j] = dp[i - 1][j];
                        b[i][j] = 2;///来自于左方
                    }
                    else
                    {
                        dp[i][j] = dp[i][j - 1];
                        b[i][j] = 3;///来自于上方
                    }
                }
            }
        }
        return ans(len1, len2, b) != "" ? ans(len1, len2, b) : "-1";
    }
};

复杂度分析：

• 时间复杂度：O(n^2)，构造辅助数组dp与b，两层循环
• 空间复杂度：O(n^2)，辅助二维数组dp与递归

方法二：栈
能够递归解决的也可以用栈解决的。
具体做法：
不需要第二个辅助数组b，直接每次比较dp与其左、上、左上的关系，然后将符合要求的字符加入栈中即可实现逆序输出。

class Solution {
public:
    string LCS(string s1, string s2) {
        if(s1.length() == 0 || s2.length() == 0) //只要有一个空字符串便不会有子序列
            return "-1";
        int len1 = s1.length();
        int len2 = s2.length();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0)); //记录最长长度
        for(int i = 1; i <= len1; i++)
        {
            for(int j = 1; j <= len2; 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]);
            }
         }
        int i=len1, j=len2;
        stack<char> s;
        while(dp[i][j])
        {
            if(dp[i][j] == dp[i - 1][j])///来自于左方向
                i--;
            else if(dp[i][j] == dp[i][j - 1])///来自于上方向
                j--;
           else if(dp[i][j]>dp[i-1][j-1])///来自于左上方向
           {
                i--;
                j--;
                s.push(s1[i]); //入栈,逆序使用
           }
        }
        string res = "";
        while(!s.empty())
        {
         res += s.top();
         s.pop();
        }
        return res != "" ? res : "-1";  //如果两个完全不同，返回字符串为空，则要改成-1
    }
};

复杂度分析：

• 时间复杂度：O(n^2)，构造辅助数组dp两层循环
• 空间复杂度：O(n^2)，辅助二维数组dp与栈空间