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的长度。
说明
- 该问题是一个经典的计算机科学问题，也是数据比较程序，比如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)，缓存部分重要数据。另外，动态规划法可以建立递归式，通过循环顺次求出最优解。
为方便说明，这里我们用 <nobr aria-hidden="true"> Xi </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mi> i </mi> </msub> </math>代表{ <nobr aria-hidden="true"> x1,x2,⋯,xi </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> x </mi> <mn> 1 </mn> </msub> <mo> , </mo> <msub> <mi> x </mi> <mn> 2 </mn> </msub> <mo> , </mo> <mo> ⋯ </mo> <mo> , </mo> <msub> <mi> x </mi> <mi> i </mi> </msub> </math>}，用 <nobr aria-hidden="true"> Yj </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mi> j </mi> </msub> </math>代表{ <nobr aria-hidden="true"> y1,y2,⋯,yj </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> y </mi> <mrow class="MJX-TeXAtom-ORD"> <mn> 1 </mn> </mrow> </msub> <mo> , </mo> <msub> <mi> y </mi> <mrow class="MJX-TeXAtom-ORD"> <mn> 2 </mn> </mrow> </msub> <mo> , </mo> <mo> ⋯ </mo> <mo> , </mo> <msub> <mi> y </mi> <mrow class="MJX-TeXAtom-ORD"> <mi> j </mi> </mrow> </msub> </math> }。那么，求长度分别为m、n的两个序列X、Y的LCS，就相当于求 <nobr aria-hidden="true"> Xm </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mi> m </mi> </msub> </math>与 <nobr aria-hidden="true"> Yn </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mi> n </mi> </msub> </math>的LCS。我们将其分割为局部问题进行分析。
首先，求 <nobr aria-hidden="true"> Xm </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mi> m </mi> </msub> </math>与 <nobr aria-hidden="true"> Yn </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mi> n </mi> </msub> </math>的LCS时要考虑以下两种情况：
当 <nobr aria-hidden="true"> xm=yn </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> x </mi> <mi> m </mi> </msub> <mo> = </mo> <msub> <mi> y </mi> <mi> n </mi> </msub> </math>时，在 <nobr aria-hidden="true"> Xm−1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mrow class="MJX-TeXAtom-ORD"> <mi> m </mi> <mo> − </mo> <mn> 1 </mn> </mrow> </msub> </math>与 <nobr aria-hidden="true"> Yn−1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mrow class="MJX-TeXAtom-ORD"> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> </mrow> </msub> </math>的LCS后面加上 <nobr aria-hidden="true"> xm(=yn) </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> x </mi> <mi> m </mi> </msub> <mo stretchy="false"> ( </mo> <mo> = </mo> <msub> <mi> y </mi> <mrow class="MJX-TeXAtom-ORD"> <mi> n </mi> </mrow> </msub> <mo stretchy="false"> ) </mo> </math>就是 <nobr aria-hidden="true"> xm </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> x </mi> <mi> m </mi> </msub> </math>与 <nobr aria-hidden="true"> yn </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> y </mi> <mi> n </mi> </msub> </math>的LCS。
举个例子，X=(a,b,c,c,d,a),Y={a, b, c, b, a}时 <nobr aria-hidden="true"> xm=yn </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> x </mi> <mi> m </mi> </msub> <mo> = </mo> <msub> <mi> y </mi> <mi> n </mi> </msub> </math>，所以在 <nobr aria-hidden="true"> Xm−1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mrow class="MJX-TeXAtom-ORD"> <mi> m </mi> <mo> − </mo> <mn> 1 </mn> </mrow> </msub> </math>与 <nobr aria-hidden="true"> Yn−1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mrow class="MJX-TeXAtom-ORD"> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> </mrow> </msub> </math>的LCS({a, b,c})后面加上 <nobr aria-hidden="true"> xm </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> x </mi> <mi> m </mi> </msub> </math> {=a) 即为 <nobr aria-hidden="true"> Xm </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mi> m </mi> </msub> </math>与 <nobr aria-hidden="true"> Yn </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mi> n </mi> </msub> </math>的LCS。
当 <nobr aria-hidden="true"> xm≠yn </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> x </mi> <mi> m </mi> </msub> <mo> ≠ </mo> <msub> <mi> y </mi> <mi> n </mi> </msub> </math>时， <nobr aria-hidden="true"> Xm−1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mrow class="MJX-TeXAtom-ORD"> <mi> m </mi> <mo> − </mo> <mn> 1 </mn> </mrow> </msub> </math>与 <nobr aria-hidden="true"> Yn </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mi> n </mi> </msub> </math>的LCS和 <nobr aria-hidden="true"> Xm </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mi> m </mi> </msub> </math>与 <nobr aria-hidden="true"> Yn−1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mrow class="MJX-TeXAtom-ORD"> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> </mrow> </msub> </math>的LCS中更长的一方就是 <nobr aria-hidden="true"> Xm </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mi> m </mi> </msub> </math>与 <nobr aria-hidden="true"> Yn </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mi> n </mi> </msub> </math>的LCS。
举个例子，X={a,b,c,c,d}, Y={a,b,c,b,a}时， <nobr aria-hidden="true"> Xm−1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mrow class="MJX-TeXAtom-ORD"> <mi> m </mi> <mo> − </mo> <mn> 1 </mn> </mrow> </msub> </math>与 <nobr aria-hidden="true"> Yn </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mi> n </mi> </msub> </math>的LCS为{a,b,c)， <nobr aria-hidden="true"> Xm </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mi> m </mi> </msub> </math>与 <nobr aria-hidden="true"> Yn </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mi> n </mi> </msub> </math>的LCS为{a,b,c,b}，因此 <nobr aria-hidden="true"> Xm </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mi> m </mi> </msub> </math>与 <nobr aria-hidden="true"> Yn−1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mrow class="MJX-TeXAtom-ORD"> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> </mrow> </msub> </math>的LCS就是 <nobr aria-hidden="true"> Xm </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mi> m </mi> </msub> </math>与 <nobr aria-hidden="true"> Yn </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mi> n </mi> </msub> </math>的LCS。
这个算法对 <nobr aria-hidden="true"> Xi </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mi> i </mi> </msub> </math>与 <nobr aria-hidden="true"> Yj </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mi> j </mi> </msub> </math>同样适用。于是可准备下述函数，用来求解LCS的局部问题。
c[m+1][n+1]: 该二维数组中，c[i][j] 代表 <nobr aria-hidden="true"> Xi </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> X </mi> <mi> i </mi> </msub> </math>与 <nobr aria-hidden="true"> Yj </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> Y </mi> <mi> j </mi> </msub> </math>的LCS的长度
c[i][j] 的值可由下述递推公式(Recursive Formula)求得。
基于上述变量和公式，可以用动态规划法求序列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:
您的提交打败了 <kbd>92.60%</kbd> 的提交.
扩展阅读:
最长公共子序列问题 - Fogsail Chen - SegmentFault 思否
https://segmentfault.com/a/1190000008521545
腾讯公司福利 465人发布
查看7道真题和解析