最长公共子序列和最长公共子串问题

最长公共子串及公共子序列问题属于一类问题,都可以使用动态规划的算法来解析,且动态规划方式比较类似,比较容易混淆。

定义

最长公共子串:两个字符串中,相同的最长子串,字符必须是连续的

最长公共子序列:两个字符串中,相同的最长序列,字符不一定是连续的

比如:a[] = “abcde” b[] = “bce”

那么:
最长子串:”bc”
最长子序列:”bce”

解法

假设A、B分别表示两个字符串

最长公共子串

dp[i][j]表示子串A[:i]、B[:j]必须以A[i]、B[j]为结尾的两个字符串的最大子串长度

1
2
3
4
5
if A[i] == B[j] {
dp[i][j] = dp[i-1][j-1]
} else {
dp[i][j] = 0
}

最终dp二维数组中的最大值即为结果

最长公共子序列

dp[i][j]表示子串A[:i]、B[:j]的两个字符串的最大子序列

1
2
3
4
5
if A[i] == B[j] {
dp[i][j] = dp[i-1][j-1]
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}

最终dp[i-1][j-1]为结果

leetcode

 wechat
欢迎订阅我的公众号!