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

最长公共子序列(二)

http://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11
题目主要信息：
  • 找到两个字符串的最长公共子序列，子序列不要求位置在原串中连续
  • 仅存在一个最长公共子序列，不需要去重
  • 最长公共子序列为空需要返回"-1"，而不是空序列，最后要变换
举一反三：

学习完本题的思路你可以解决如下题目：

BM66.最长公共子串

BM71.最长上升子序列(一)

BM73 最长回文子串

BM75 编辑距离(一)

BM76 正则表达式匹配

BM77 最长的括号子串

方法一：动态规划+递归获取（推荐使用）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

思路：

题目要求获取最长公共子序列，我们肯定要先知道最长到底是多长，因此肯定要先求最长公共子序列的长度，然后根据这个长度获取这个子序列。（注意：子序列不是子串，子串要求所有字符必须连续，子序列不要求连续，只要求相对位置不变）

具体做法：

  • step 1：优先检查特殊情况。
  • step 2：获取最长公共子序列的长度可以使用动态规划，我们以dp[i][j]dp[i][j]表示在s1中以ii结尾，s2中以jj结尾的字符串的最长公共子序列长度。
  • step 3：遍历两个字符串的所有位置，开始状态转移：若是ii位与jj位的字符相等，则该问题可以变成1+dp[i−1][j−1]1+dp[i-1][j-1]，即到此处为止最长公共子序列长度由前面的结果加1。
  • step 4：若是不相等，说明到此处为止的子串，最后一位不可能同时属于最长公共子序列，毕竟它们都不相同，因此我们考虑换成两个子问题，dp[i][j−1]dp[i][j-1]或者dp[i−1][j]dp[i-1][j]，我们取较大的一个就可以了，由此感觉可以用递归解决。
  • step 5：但是递归的复杂度过高，重复计算了很多低层次的部分，因此可以用动态规划，从前往后加，由此形成一个表，表从位置1开始往后相加，正好符合动态规划的转移特征。
  • step 6：因为最后要返回该序列，而不是长度，所以在构造表的同时要以另一个二维矩阵记录上面状态转移时选择的方向，我们用1表示来自左上方，2表示来自左边，3表示来自上边。
  • step 7：获取这个序列的时候，根据从最后一位开始，根据记录的方向，不断递归往前组装字符，只有来自左上的时候才添加本级字符，因为这种情况是动态规划中两个字符相等的情况，字符相等才可用。

图示：

图片说明

Java实现代码：

import java.util.*;
public class Solution {
    private String x = "";
    private String y = "";
    //获取最长公共子序列
    String ans(int i, int j, 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.charAt(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;
    }
    public 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;
        //dp[i][j]表示第一个字符串到第i位，第二个字符串到第j位为止的最长公共子序列长度
        int[][] dp = new int[len1 + 1][len2 + 1];
        //动态规划数组相加的方向
        int[][] b = new int[len1 + 1][len2 + 1];
        //遍历两个字符串每个位置求的最长长度
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                //遇到两个字符相等
                if(s1.charAt(i - 1) == s2.charAt(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;
                    }
                }
            }
        }
        //获取答案字符串
        String res = ans(len1, len2, b);
        //检查答案是否位空
        if(res.isEmpty()) 
            return "-1";
        else
            return res;
    }
}

C++实现代码：

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;
        //dp[i][j]表示第一个字符串到第i位，第二个字符串到第j位为止的最长公共子序列长度
        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;
                    }
                }
            }
        }
        //获取答案字符串
        string res = ans(len1, len2, b);
        //检查答案是否位空
        return  res != "" ? res : "-1";
    }
};

Python代码实现：

import sys
#设置递归深度
sys.setrecursionlimit(100000) 
class Solution:
    def __init__(self):
        self.x = ""
        self.y = ""
    #获取最长公共子序列
    def ans(self, i: int, j: int, b: List[List[int]]): 
        res = ""
        #递归终止条件
        if i == 0 or j == 0: 
            return res
        #根据方向，往前递归，然后添加本级字符
        if b[i][j] == 1:
            res = res + self.ans(i - 1, j - 1, b)
            res = res + self.x[i - 1]
        elif b[i][j] == 2:
            res = res + self.ans(i - 1, j, b)
        elif b[i][j] == 3:
            res = res + self.ans(i, j - 1, b)
        return res
    def LCS(self , s1: str, s2: str) -> str:
        #特殊情况
        if s1 is None or s2 is None: 
            return "-1"
        len1 = len(s1)
        len2 = len(s2)
        self.x = s1
        self.y = s2
        #dp[i][j]表示第一个字符串到第i位，第二个字符串到第j位为止的最长公共子序列长度
        dp = [[0] * (len2 + 1) for i in range(len1 + 1)]
        #动态规划数组相加的方向
        b = [[0] * (len2 + 1) for i in range(len1 + 1)]
        #遍历两个字符串每个位置求的最长长度
        for i in range(1, len1 + 1): 
            for j in range(1, len2 + 1):
                #遇到两个字符相等
                if s1[i - 1] == s2[j - 1]:
                    #考虑由二者都向前一位
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    #来自于左上方
                    b[i][j] = 1 
                #遇到的两个字符不同
                #左边的选择更大，即第一个字符串后退一位
                elif 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 
        #获取答案字符串
        res = self.ans(len1, len2, b)
        #检查答案是否位空
        if res is None or res == "":
            return "-1"
        else:
            return res

复杂度分析：

  • 时间复杂度：O(n2)O(n^2)，构造辅助数组dp与b，两层循环，递归是有方向的递归，因此只是相当于遍历了二维数组
  • 空间复杂度：O(n2)O(n^2)，辅助二维数组dp与递归栈的空间最大为O(n2)O(n^2)
方法二：动态归划+栈获取（扩展思路）

知识点1：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

知识点2：栈

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

思路：

能够递归解决的也可以用栈解决的，递归实现将问题缩小往前，然后将符合条件的字符依次拼接，栈也可以实现。

具体做法：

  • step 1：优先检查特殊情况。
  • step 2：获取最长公共子序列的长度可以使用动态规划，我们以dp[i][j]dp[i][j]表示在s1中以ii结尾，s2中以jj结尾的字符串的最长公共子序列长度。
  • step 3：遍历两个字符串的所有位置，开始状态转移：若是ii位与jj位的字符相等，则该问题可以变成1+dp[i−1][j−1]1+dp[i-1][j-1]，即到此处为止最长公共子序列长度由前面的结果加1。
  • step 4：若是不相等，说明到此处为止的子串，最后一位不可能同时属于最长公共子序列，毕竟它们都不相同，因此我们考虑换成两个子问题，dp[i][j−1]dp[i][j-1]或者dp[i−1][j]dp[i-1][j]，我们取较大的一个就可以了。
  • step 5：得到最长长度后，获取不需要第二个辅助数组b，直接从dp数组最后一位开始，每次比较当前位置与其左、上、左上的关系，然后将符合要求的字符加入栈中，符合要求即来自dp表格左上方的字符。
  • step 6：最后将栈中的字符拼接即可得到最长公共子序列，注意检查子序列是否为空。

Java实现代码：

import java.util.*;
public 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();
        //dp[i][j]表示第一个字符串到第i位，第二个字符串到第j位为止的最长公共子序列长度
        int[][] dp = new int[len1 + 1][len2 + 1]; 
        //遍历两个字符串每个位置求的最长长度
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                //遇到两个字符相等
                if(s1.charAt(i - 1) == s2.charAt(j - 1))
                    //来自于左上方
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                //遇到的两个字符不同
                else
                    //来自左边或者上方的最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        //从动态规划数组末尾开始
        int i = len1, j = len2;
        Stack<Character> s = new Stack<Character>();
        while(dp[i][j] != 0){
            //来自于左方向
            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.charAt(i)); 
           }
        }
        String res = "";
        //拼接子序列
        while(!s.isEmpty())
            res += s.pop();
        //如果两个完全不同，返回字符串为空，则要改成-1
        return !res.isEmpty() ? res : "-1";  
    }
}

C++实现代码：

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();
        //dp[i][j]表示第一个字符串到第i位，第二个字符串到第j位为止的最长公共子序列长度
        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();
        }
        //如果两个完全不同，返回字符串为空，则要改成-1
        return res != "" ? res : "-1";  
    }
};

Python代码实现：

class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        #特殊情况
        if s1 is None or s2 is None: 
            return "-1"
        len1 = len(s1)
        len2 = len(s2)
        #dp[i][j]表示第一个字符串到第i位，第二个字符串到第j位为止的最长公共子序列长度
        dp = [[0] * (len2 + 1) for i in range(len1 + 1)] 
        #遍历两个字符串每个位置求的最长长度
        for i in range(1, len1 + 1):
            for j in range(1, len2 + 1):
                #遇到两个字符相等
                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])
        #从动态规划数组末尾开始
        i = len1
        j = len2
        s = []
        while dp[i][j] != 0:
            #来自于左方向
            if dp[i][j] == dp[i - 1][j]: 
                i = i - 1
            #来自于上方向
            elif dp[i][j] == dp[i][j - 1]: 
                j = j - 1
            #来自于左上方向
            elif dp[i][j] > dp[i - 1][j - 1]: 
                i = i - 1
                j = j - 1
                #只有左上方向才是字符相等的情况，入栈，逆序使用
                s.append(s1[i]) 
        res = ""
        #拼接子序列
        while len(s) != 0:
            res += s[-1]
            s.pop()
        #如果两个完全不同，返回字符串为空，则要改成-1
        if res is None or res == "": 
            return "-1"
        else:
            return res

复杂度分析：

  • 时间复杂度：O(n2)O(n^2)，最坏复杂度为构造辅助数组dp两层循环
  • 空间复杂度：O(n2)O(n^2)，辅助二维数组dp与栈空间最大为O(n2)O(n^2)
全部评论
这非要放个播这么快的gif是生怕我们看清楚里面的内容吗
15 回复 分享
发布于 2022-09-17 22:35 美国
博主上和左搞反了
3 回复 分享
发布于 2022-08-31 11:04 浙江
图示都是错的
2 回复 分享
发布于 2022-06-21 02:33
这个题的答案似乎有点问题，测试数据中有一个示例我得到一个与答案不同但是长度相同的结果
1 回复 分享
发布于 2023-04-21 18:23 吉林
好家伙，图都是错的
点赞 回复 分享
发布于 2022-07-22 15:42
// C++ 用一个dp数组记录最终string结果 ，内存会超 string LCS(string s1, string s2) { // write code here vector<vector><string>> dp(s1.size(), vector<string>(s2.size(), "")); for (int i1 = 0; i1 < s1.size(); ++i1) { if (s1[i1] == s2[0]) { dp[i1][0] = s1[i1]; } } for (int i2 = 0; i2 < s2.size(); ++i2) { if (s2[i2] == s1[0]) { dp[0][i2] = s2[i2]; } } for (int i1 = 1; i1 < s1.size(); ++i1) { for (int i2 = 1; i2 < s2.size(); ++i2) { if (s1[i1] == s2[i2]) { dp[i1][i2] = dp[i1 - 1][i2 - 1] + s1[i1]; }else { if (dp[i1 - 1][i2].size() > dp[i1][i2 - 1].size()) { dp[i1][i2] = dp[i1 - 1][i2]; } else { dp[i1][i2] = dp[i1][i2 - 1]; } } } } if (dp[s1.size() - 1][s2.size() - 1] == "") return "-1"; return dp[s1.size() - 1][s2.size() - 1]; }</string></string></vector>
点赞 回复 分享
发布于 2022-08-11 12:36
C++实现代码左边和上边写反了
点赞 回复 分享
发布于 2023-03-28 15:54 湖北
图里面的4是啥意思
点赞 回复 分享
发布于 2023-04-13 17:33 浙江
两层for循环，对于每个遍历的情况都向前，在已经得到的结果基础上（dp二维数组，分三种情况）给出答案，并使用b数组来记录怎么得到的。 接着ans函数从后往前递归查询b数组，就是动图的那种就可以得到结果 还容易搞混的就是dp数组有第一列第一行为0的初始情况，二维数组下标与字符串数组小标差了1
点赞 回复 分享
发布于 2023-05-20 12:37 北京
dp[1][0]和dp[0][1]怎么算的呢？
点赞 回复 分享
发布于 2023-05-20 20:00 福建
动图是错的，按照他这么拼接根本得不出正确答案
点赞 回复 分享
发布于 2023-10-24 14:29 广东
Orz
点赞 回复 分享
发布于 08-14 14:26 北京
代码运行超时了
点赞 回复 分享
发布于 08-28 09:55 天津

相关推荐

11-20 00:09
山西大学 OTA系统工程师
点赞 评论 收藏
分享
11-20 12:02
门头沟学院 产品经理
点赞 评论 收藏
分享
11-20 11:11
门头沟学院 后勤
点赞 评论 收藏
分享
10-16 11:41
武汉理工大学 机械设计/制造
点赞 评论 收藏
分享
11-15 15:37
门头沟学院 软件测试
运营也这么难吗
牛客146600443号：92的能看上这3k，5k在搞笑呢
点赞 评论 收藏
分享
58 21 评论
分享

全站热榜

正在热议
# 晒一晒我的offer #
9702311次浏览 104815人参与
# 机械只有读研才有出路吗？ #
7863次浏览 103人参与
# 北方华创开奖 #
20995次浏览 244人参与
# 地方国企笔面经互助 #
1870次浏览 6人参与
# 滴滴求职进展汇总 #
78660次浏览 687人参与
# 考研失败就一定是坏事吗？ #
36225次浏览 355人参与
# 机械人，签完三方你在忙什么？ #
22916次浏览 119人参与
# 总结:哪家公司面试体验感最差 #
23361次浏览 115人参与
# 机械应届生薪资要多少才合适？ #
11710次浏览 55人参与
# 学历or实习经历，哪个更重要 #
39017次浏览 280人参与
# 选完offer后，你后悔学本专业吗 #
6454次浏览 43人参与
# 查收我的offer竞争力报告 #
13139次浏览 191人参与
# 机械人怎么评价今年的比亚迪 #
40832次浏览 141人参与
# 应届生被毁约被毁意向了怎么办 #
23936次浏览 228人参与
# 00后45度躺现状 #
33274次浏览 294人参与
# 没有合适的工作，你会先找个干着，还是考公考研 #
35257次浏览 392人参与
# 秋招OC许愿 #
223884次浏览 1853人参与
# 如果能重来，就业or读研你选哪个？ #
45211次浏览 333人参与
# 大疆求职进展汇总 #
402559次浏览 2869人参与
# 实习，投递多份简历没人回复怎么办 #
2381058次浏览 34162人参与
# 双非能在秋招上岸吗？ #
98698次浏览 768人参与
牛客网
牛客企业服务