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)，缓存部分重要数据。另外，动态规划法可以建立递归式，通过循环顺次求出最优解。
为方便说明，这里我们用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的两个序列X、Y的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)求得。
基于上述变量和公式，可以用动态规划法求序列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
最新文章
- ASP.net 页面生命周期
- 【BZOJ1671】[Usaco2005 Dec]Knights of Ni 骑士 BFS
- AutoIt3（AU3）开发的智能驱动安装工具，用于系统封装，支持参数静默启动
- css003 选择器：明确设置哪些样式
- iOS 杂笔-21（self.name = “object” 和 _name =”object” 有什么不同？）
- Android技能杂谈——如何优雅的处理控件的点击事件
- 161017、SQL必备知识点
- JAVA学习篇--javaweb之Filter具体解释
- Querylayer(查询图层) - 浅谈
- MyEclipse 2014 破解版下载：我有，需要的给我说一声，给你发过去
- sshpass笔记
- Axure如何建立共享项目、如何编辑共享项目、如何获取共享项目
- JMeter5.1企业级应用应用常用功能详解（含插件安装）
- git pull报“unable to update local ref”解决方案
- new和delete重载
- JavaScript初探三
- ios中二维码的用法
- （原创）C++11改进我们的程序之move和完美转发
- mysql5.7密码设置
- iterm2用法与技巧