C++版 - Lintcode 77-Longest Common Subsequence最长公共子序列(LCS) - 题解

版权声明:本文为博主Bravo Yeung(知乎UserName同名)的原创文章,欲转载请先私信获博主允许,转载时请附上网址

http://blog.csdn.net/lzuacm

C++版 - Lintcode 77-Longest Common Subsequence最长公共子序列(LCS) - 题解

在线提交(不支持C#):

https://www.lintcode.com/problem/longest-common-subsequence/

题目描述

一个字符串的一个子序列是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。例如,”ACE” 是 “ABCDE” 的一个子序列,而 “AEC” 不是)。

给出两个字符串,找到最长公共子序列(LCS),返回LCS的长度。

说明

样例

给出“ABCD”“EDCA”,这个LCS是 “A” (或 D或C),返回1

给出 “ABCD”“EACB”,这个LCS是“AC”返回 2

注意

序列可以不连续。


  ● Difficulty: Medium
  • Total Accepted: 18202

  • Total Submitted: 45985

  • Accepted Rate: 39%

Tags:

Longest Common Subsequence

LintCode Copyright

Dynamic Programming(DP)

分析:

将算式的计算结果记录在内存中,需要时直接调用该结果,从而避免无用的重复计算,提高处理效率,这在程序和算法设计中是一种行之有效的手法。动态规划就是这类手法之一。

事实上动态规划是一种记忆化递归(memorized recursive),缓存部分重要数据。另外,动态规划法可以建立递归式,通过循环顺次求出最优解。

为方便说明,这里我们用Xi" role="presentation">XiXi代表{x1,x2,⋯,xi" role="presentation">x1,x2,⋯,xix1,x2,⋯,xi},用Yj" role="presentation">YjYj代表{y1,y2,⋯,yj" role="presentation">y1,y2,⋯,yjy1,y2,⋯,yj }。那么,求长度分别为m、n的两个序列XY的LCS,就相当于求Xm" role="presentation">XmXm与Yn" role="presentation">YnYn的LCS。我们将其分割为局部问题进行分析。

首先,求Xm" role="presentation">XmXm与Yn" role="presentation">YnYn的LCS时要考虑以下两种情况:

  • 当xm=yn" role="presentation">xm=ynxm=yn时,在Xm−1" role="presentation">Xm−1Xm−1与Yn−1" role="presentation">Yn−1Yn−1的LCS后面加上xm(=yn)" role="presentation">xm(=yn)xm(=yn)就是xm" role="presentation">xmxm与yn" role="presentation">ynyn的LCS。

    举个例子,X=(a,b,c,c,d,a),Y={a, b, c, b, a}时xm=yn" role="presentation">xm=ynxm=yn,所以在Xm−1" role="presentation">Xm−1Xm−1与Yn−1" role="presentation">Yn−1Yn−1的LCS({a, b,c})后面加上xm" role="presentation">xmxm {=a) 即为Xm" role="presentation">XmXm与Yn" role="presentation">YnYn的LCS。

  • 当xm≠yn" role="presentation">xm≠ynxm≠yn时,Xm−1" role="presentation">Xm−1Xm−1与Yn" role="presentation">YnYn的LCS和Xm" role="presentation">XmXm与Yn−1" role="presentation">Yn−1Yn−1的LCS中更长的一方就是Xm" role="presentation">XmXm与Yn" role="presentation">YnYn的LCS。

    举个例子,X={a,b,c,c,d}, Y={a,b,c,b,a}时,Xm−1" role="presentation">Xm−1Xm−1与Yn" role="presentation">YnYn的LCS为{a,b,c),Xm" role="presentation">XmXm与Yn" role="presentation">YnYn的LCS为{a,b,c,b},因此Xm" role="presentation">XmXm与Yn−1" role="presentation">Yn−1Yn−1的LCS就是Xm" role="presentation">XmXm与Yn" role="presentation">YnYn的LCS。

这个算法对Xi" role="presentation">XiXi与Yj" role="presentation">YjYj同样适用。于是可准备下述函数,用来求解LCS的局部问题。

c[m+1][n+1]: 该二维数组中,c[i][j] 代表Xi" role="presentation">XiXi与Yj" role="presentation">YjYj的LCS的长度

c[i][j] 的值可由下述递推公式(Recursive Formula)求得。

c[i][j]={0i=0 || j=0c[i−1][j−1]+1i,j>0 and xi=yjmax(c[i][j−1],c[i−1][j])i,j>0 and xi≠yj" role="presentation">c[i][j]=⎧⎩⎨0c[i−1][j−1]+1max(c[i][j−1],c[i−1][j])i=0 || j=0i,j>0 and xi=yji,j>0 and xi≠yjc[i][j]={0i=0 || j=0c[i−1][j−1]+1i,j>0 and xi=yjmax(c[i][j−1],c[i−1][j])i,j>0 and xi≠yj

基于上述变量和公式,可以用动态规划法求序列XY的LCS。

已AC代码如下:

class Solution {
public:
    int longestCommonSubsequence(string &A, string &B) {
        int m = A.size();
        int n = B.size();

        int **c = (int **)malloc((m+1) * sizeof(int *));
        for (int i = 0; i < m + 1; i++)
            c[i] = (int *)malloc((n+1) * sizeof(int));

        int max1 = 0;
        A = ' ' + A;
        B = ' ' + B;
        for (size_t i = 1; i <= m; i++)
            c[i][0] = 0;
        for (size_t j = 1; j <= n; j++)
            c[0][j] = 0;

        for (size_t i = 1; i <= m; i++)
        {
            for (size_t j = 0; j <= n; j++)
            {
                if (A[i] == B[j])
                {
                    c[i][j] = c[i - 1][j - 1] + 1;
                }
                else
                    c[i][j] = max(c[i][j - 1], c[i - 1][j]);
                max1 = max(max1, c[i][j]);
            }
        }
        return max1;
    }
};

Rank:

您的提交打败了 92.60% 的提交.

扩展阅读:

最长公共子序列问题 - Fogsail Chen - SegmentFault 思否

https://segmentfault.com/a/1190000008521545

上一篇:【架构师面试-云原生-2】-云原生面试之Kubernetes(k8s)面试题大全100题


下一篇:一些漂亮的js库