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

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

在线提交(不支持C#): https://www.lintcode.com/problem/longest-common-subsequence/

题目描述

一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）。 给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。

说明

• 该问题是一个经典的计算机科学问题，也是数据比较程序，比如Diff工具。它也被广泛地应用在版本控制，比如Git用它来协调文件之间的改变。它还是生物信息学应用的基础。
• https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

样例 给出“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)，缓存部分重要数据。另外，动态规划法可以建立递归式，通过循环顺次求出最优解。

为方便说明，这里我们用XiXiX_i代表{x1,x2,⋯,xix1,x2,⋯,xix_1,x_2,\cdots,x_i}，用YjYjY_j代表{y1,y2,⋯,yjy1,y2,⋯,yjy_{1},y_{2},\cdots,y_{j} }。那么，求长度分别为m、n的两个序列X、Y的LCS，就相当于求XmXmX_m与YnYnY_n的LCS。我们将其分割为局部问题进行分析。

首先，求XmXmX_m与YnYnY_n的LCS时要考虑以下两种情况：

• 当xm=ynxm=ynx_m=y_n时，在Xm−1Xm−1X_{m-1}与Yn−1Yn−1Y_{n-1}的LCS后面加上xm(=yn)xm(=yn)x_m(=y_{n})就是xmxmx_m与ynyny_n的LCS。 举个例子，X=(a,b,c,c,d,a),Y={a, b, c, b, a}时xm=ynxm=ynx_m=y_n，所以在Xm−1Xm−1X_{m-1}与Yn−1Yn−1Y_{n-1}的LCS({a, b,c})后面加上xmxmx_m {=a) 即为XmXmX_m与YnYnY_n的LCS。
• 当xm≠ynxm≠ynx_m≠y_n时，Xm−1Xm−1X_{m-1}与YnYnY_n的LCS和XmXmX_m与Yn−1Yn−1Y_{n-1}的LCS中更长的一方就是XmXmX_m与YnYnY_n的LCS。 举个例子，X={a,b,c,c,d}, Y={a,b,c,b,a}时，Xm−1Xm−1X_{m-1}与YnYnY_n的LCS为{a,b,c)，XmXmX_m与YnYnY_n的LCS为{a,b,c,b}，因此XmXmX_m与Yn−1Yn−1Y_{n-1}的LCS就是XmXmX_m与YnYnY_n的LCS。

这个算法对XiXiX_i与YjYjY_j同样适用。于是可准备下述函数，用来求解LCS的局部问题。

c[m+1][n+1]: 该二维数组中，c[i][j] 代表XiXiX_i与YjYjY_j的LCS的长度

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

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

c[i][j]=\begin{cases} 0 & i = 0 \ || \ j =0 \\ c[i-1][j-1] + 1 & i,j >0 \ and \ x_i = y_{j} \\ max(c[i][j-1], c[i-1][j]) & i,j >0 \ and \ x_i ≠ y_{j} \end{cases}

基于上述变量和公式，可以用动态规划法求序列X与Y的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