欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最长公共子序列、最长连续公共子序列、最长递增子序列

程序员文章站 2022-07-16 11:41:29
...

面试中除了排序问题,还会经常出现字符串的子序列问题,这里讲解使用动态规划解决三个常见的子序列问题:
1、最长公共子序列问题(LCS,longest-common-subsequence problem)
2、最长连续公共子序列问题
3、最长递增子序列(LIS,longest-increment-subsequence)

最长公共子序列问题LCS

问题描述:

给定两个序列X=<x1,x2,...,xm>和Y=<y1,y2,...,yn>,求X和Y的最长公共子序列。(子序列可以是不连续的,比如{B,C,D,B}就是{A,B,C,B,D,A,B}的子序列)
例如:输入两个字符串 BDCABA 和 ABCBDAB,字符串 BCBA 和 BDAB 都是是它们的最长公共子序列,则输出它们的长度 4,并打印任意一个子序列。

动态规划

时间复杂度O(M*N),空间复杂度O(M*N)。

在使用动态规划之前先规定一下符号,给定一个序列X=<x1,x2,...,xm>,定义Xi为X的前缀,即Xi=<x1,x2,...,xi>。

在求X=<x1,x2,...,xm>和Y=<y1,y2,...,yn>的一个LCS时,我们需要求解一个或者两个子问题。如果xm=yn,那么我们应该求解xm1=yn1的一个LCS。如果xmyn,我们必须求解两个子问题:求Xm1Y的一个LCS与XYn1的一个LCS。两个LCS中较长的一个,即为X和Y的一个LCS,经过推理可知,这些子情况覆盖了所有可能出现的情况。

所以递推公式为:

最长公共子序列、最长连续公共子序列、最长递增子序列

具体到实际的例子中:

最长公共子序列、最长连续公共子序列、最长递增子序列

代码

public class LCS {

    public static int[][] lengthofLCS(char[] X, char[] Y){
        /* 构造二维数组c[][]记录X[i]和Y[j]的LCS长度 (i,j)是前缀
         * c[i][j]=0; 当 i = j = 0;
         * c[i][j]=c[i-1][j-1]+1; 当 i = j > 0; Xi == Y[i]
         * c[i][j]=max(c[i-1][j],c[i][j+1]); 当 i = j > 0; Xi != Y[i]
         * 需要计算 m*n 个子问题的长度 即 任意c[i][j]的长度
         * -- 填表过程
         */
        int[][]c = new int[X.length+1][Y.length+1];

        // 动态规划计算所有子问题
        for(int i=1;i<=X.length;i++){
            for (int j=1;j<=Y.length;j++){
                if(X[i-1]==Y[j-1]){
                    c[i][j] = c[i-1][j-1]+1;
                }
                else if(c[i-1][j] >= c[i][j-1]){
                    c[i][j] = c[i-1][j];
                }
                else{
                    c[i][j] = c[i][j-1];
                }
            }
        }

        // 打印C数组
        for(int i=0;i<=X.length;i++){
            for (int j=0;j<=Y.length;j++){
                System.out.print(c[i][j]+" ");
            }
            System.out.println();
        }
        return c;
    }
    // 输出LCS序列
    public static void print(int[][] arr, char[] X, char[] Y, int i, int j) {
        if(i == 0 || j == 0)
            return;
        if(X[i-1] == Y[j-1]) {
            System.out.print("element " + X[i-1] + " ");

            print(arr, X, Y, i-1, j-1);
        }else if(arr[i-1][j] >= arr[i][j-1]) {
            print(arr, X, Y, i-1, j);
        }else{
            print(arr, X, Y, i, j-1);
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        char[] x ={'A','B','C','B','D','A','B'}; 
        char[] y ={'B','D','C','A','B','A'}; 
        int[][] c = lengthofLCS(x,y);
        print(c, x, y, x.length, y.length);
    }
}

最长公共连续子序列(最长公共子串)

问题描述

给定两个序列X=<x1,x2,...,xm>和Y=<y1,y2,...,yn>,求X和Y的最长公共公共子序列。(连续子序列必须连续的)
例如:输入两个字符串 acbac和 acaccbabb,则最大连续子串为 “cba”, 则返回长度 3。

动态规划

时间复杂度O(M*N),空间复杂度O(M*N)。

这个 LCS 跟前面说的最长公共子序列的 LCS 不一样,不过也算是 LCS 的一个变体,在 LCS 中,子序列是不必要求连续的,而子串则是 “连续” 的。

我们还是像之前一样 “从后向前” 考虑是否能分解这个问题,类似最长公共子序列的分析,这里,我们使用c[i,j] 表示 以 Xi 和 Yj 结尾的最长公共子串的长度,因为要求子串连续,所以对于 Xi 与 Yj 来讲,它们要么与之前的公共子串构成新的公共子串;要么就是不构成公共子串。故状态转移方程:

最长公共子序列、最长连续公共子序列、最长递增子序列

代码

public class LCString {
    public  static int lengthofLCString(String X, String Y){
        /* 构造二维数组c[][]记录X[i]和Y[j]的LCS长度 (i,j)是前缀
         * c[i][j]=0; 当 i = j = 0;
         * c[i][j]=c[i-1][j-1]+1; 当 i = j > 0; Xi == Y[i]
         * c[i][j]=0; 当 i = j > 0; Xi != Y[i]
         * 需要计算 m*n 个子问题的长度 即 任意c[i][j]的长度
         * -- 填表过程
         */
        int[][]c = new int[X.length()+1][Y.length()+1];
        int maxlen = 0;
        int maxindex = 0;
        for(int i =1;i<=X.length();i++){
            for(int j=1;j<=Y.length();j++){
                if(X.charAt(i-1) == Y.charAt(j-1)){
                    c[i][j] = c[i-1][j-1]+1;
                    if(c[i][j] > maxlen)
                    {
                        maxlen = c[i][j];
                        maxindex = i + 1 - maxlen;
                    }
                }
            }
        }
        return maxlen;
    }

    public static void main(String[] args) {
        String X = "acbac";
        String Y = "acaccbabb";
        System.out.println(lengthofLCString(X,Y)); 
    }
}

最长递增子序列(longest-common-subsequence)

问题描述

给定一个序列X=<x1,x2,...,xm>,求X的最长递增子序列。(子序列可以是不连续的,比如{5,6,7,1,2,8} 的LIS是5,6,7,8

动态规划

时间复杂度O(N^2),空间复杂度O(N)。
DP[i]怎么计算?
遍历所有j < i的元素,检查是否DP[j]+1>DP[i] && arr[j] < arry[i] 若是,则可以更新DP[i]

以{5,6,7,1,2,8} 的LIS是5,6,7,8举例:

最长公共子序列、最长连续公共子序列、最长递增子序列

如何选取DP[5]的值呢?就是在所有8之前的小于8的值(即j < i && arr[j] < arry[i])中,选择dp[j]最大的值,
DP[i] = DP[j] + 1

DP[5] = DP[2] + 1 = 3 + 1 = 4

代码

int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;

for (int i = 1; i < N; i++)
{
   DP[i] = 1;
   prev[i] = -1;

   for (int j = i - 1; j >= 0; j--)
      if (DP[j] + 1 > DP[i] && array[j] < array[i])
      {
         DP[i] = DP[j] + 1;
         prev[i] = j;
      }

   if (DP[i] > maxLength)
   {
      bestEnd = i;
      maxLength = DP[i];
   }