golang刷leetcode动态规划（2）最长公共子串（子序列）
golang刷leetcode动态规划（2）最长公共子串（子序列）
最长公共子串与最长公共子序列
子串（Substring）是串的一个连续的部分，子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串acdfg同akdfc的最长公共子串为df，而他们的最长公共子序列是adf。
最长公共子串
假设已知s1[0:i－1],s2[0:j－1]从右往左数的最长公共子串长度，那么两字符串同时右移一位，如果s1[i]==s2[j],则s1[0:i],s2[0:j]在i，j位置的最长公共子串长度是s1[0:i－1],s2[0:j－1]从右往左数的最长公共子串长度＋1，否则是0，用a[i][j]记录此长度，状态转移方程如下：
if s1[i]==s2[j]{
a[i][j]=a[i-1][j-1]+1
}else{
a[i][j]=0
}
用到了i-1,j-1,所以两个都递增，初始化都为0，如果两个首字母相同a[0][0:j]=1,a[0:i][0]=1
func Lcs(s1 string, s2 string) string {
if len(s1) == 0 || len(s2) == 0 {
return ""
}
a := make([][]int, len(s1))
for i := 0; i < len(s1); i++ {
a[i] = make([]int, len(s2))
if []byte(s1)[i] == []byte(s2)[0] {
a[i][0] = 1
}
}
for j := 1; j < len(s2); j++ {
if []byte(s1)[0] == []byte(s2)[j] {
a[0][j] = 1
}
}
max := 0
ii := 0
jj := 0
for i := 1; i < len(s1); i++ {
for j := 1; j < len(s2); j++ {
if []byte(s1)[i] == []byte(s2)[j] {
a[i][j] = a[i-1][j-1] + 1
}
if a[i][j] > max {
max = a[i][j]
ii = i
jj = j
}
}
}
return string([]byte(s1)[ii+1-a[ii][jj] : ii+1])
}最长公共子序列
假设已知s1[0:i-1],s2[0:j-1]的最长公共子序列，如果s1[i]==s2[j],则，s1[0:i],s2[0:j]的长度为s1[0:i-1],s2[0:j-1]的最长公共子序列＋1，否则取s1[0:i],s2[0:j-1] 与s1[0:i-1],s2[0:j]中的大者，同a[i][j]记录最长公共子序列的长度，状态转移方程为：
if s1[i]==s2[j]{
a[i][j]=a[i-1][j-1]+1
}else{
a[i][j]=max(a[]i)[j-1],a[i-1][j])
}
用到了i-1,j-1,所以两个都递增，初始化都为0，如果两个首字母相同a[0][0:j]=1,a[0:i][0]=1
func Lcs(s1 string, s2 string) int {
if len(s1) == 0 || len(s2) == 0 {
return 0
}
a := make([][]int, len(s1))
for i := 0; i < len(s1); i++ {
a[i] = make([]int, len(s2))
if []byte(s1)[i] == []byte(s2)[0] {
a[i][0] = 1
}
}
for j := 1; j < len(s2); j++ {
if []byte(s1)[0] == []byte(s2)[j] {
a[0][j] = 1
}
}
max := 0
for i := 1; i < len(s1); i++ {
for j := 1; j < len(s2); j++ {
if []byte(s1)[i] == []byte(s2)[j] {
a[i][j] = a[i-1][j-1] + 1
} else if a[i][j-1] > a[i-1][j] {
a[i][j] = a[i][j-1]
} else {
a[i][j] = a[i-1][j]
}
if a[i][j] > max {
max = a[i][j]
}
}
}
return max
}本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
腾讯云开发者
