最长公共子序列(LCS)
定义 (维基百科)
【最长公共子序列(LCS)】在一个序列集合中(通常为两个序列)查找所有序列中最长的子序列。
这与查找最长公共子串的问题不同的地方是:子序列不需要在原序列中占用连续的位置。
最长公共子序列问题是一个经典的计算机科学问题,解决方案 这类问题通常都是采用动态规划的思想来解决,核心就是构造出动态解决方程。
也是数据比较程序,比如 Diff工具 和 生物信息学应用的基础。
它也被广泛地应用在 版本控制,比如Git用来调和文件之间的改变
以两个序列 X、Y 为例子:
设有二维数组dp[i,j]表示X的第i位和Y的第j位之前的最长公共子序列的长度,则有:
$$ dp[i,j]= \begin{cases} dp[i-1][j-1]+1& \text{(X[i]==Y[j])}\\ max\{dp[i-1,j],dp[i,j-1]\}& \text{(X[i]!=Y[j])} \end{cases} $$
时间复杂度和空间复杂度都是O(mn)。力扣水题
func longestCommonSubsequence(text1 string, text2 string) int {
len1, len2 := len(text1), len(text2)
if len1 == 0 || len2 == 0 {
return 0
}commonSub := make([][]int, len1+1, len1+1)
// 初始化二维数据
for i := 0;
i <= len1;
i++ {
commonSub[i] = make([]int, len2+1, len2+1)
}for i := 0;
i < len1;
i++ {
for j := 0;
j < len2;
j++ {
if text1[i] == text2[j] {
commonSub[i+1][j+1] = commonSub[i][j] + 1
} else {
commonSub[i+1][j+1] = max(commonSub[i][j+1], commonSub[i+1][j])
}
}
}
return commonSub[len1][len2]
}func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
推荐阅读
- 2018年11月19日|2018年11月19日 星期一 亲子日记第144篇
- 遇到一哭二闹三打滚的孩子,怎么办┃山伯教育
- 这辈子我们都不要再联系了
- 2019年12月24日
- Ⅴ爱阅读,亲子互动——打卡第178天
- 眼观耳听美食的日子
- 子龙老师语录
- 成交的种子咖啡冥想
- 2018年9月5日,星期三,天气晴
- 生活随笔|好天气下的意外之喜