剑指OfferII095.最长公共子序列
发布于 2021-10-17 00:32
剑指OfferII095.最长公共子序列
01
—
题目
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：
它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
02
—
解题思路分析
1、动态规划；时间复杂度O(n^2)，空间复杂度O(n^2)
func longestCommonSubsequence(text1 string, text2 string) int {n, m := len(text1), len(text2)dp := make([][]int, n+1)for i := 0; i < n+1; i++ {dp[i] = make([]int, m+1)}for i := 1; i <= n; i++ {for j := 1; j <= m; j++ {if text1[i-1] == text2[j-1] {dp[i][j] = dp[i-1][j-1] + 1} else {dp[i][j] = max(dp[i][j-1], dp[i-1][j])}}}return dp[n][m]}func max(a, b int) int {if a > b {return a}return b}
2、动态规划；时间复杂度O(n^2)，空间复杂度O(n)
func longestCommonSubsequence(text1 string, text2 string) int {n, m := len(text1), len(text2)prev := make([]int, m+1)cur := make([]int, m+1)for i := 1; i <= n; i++ {for j := 1; j <= m; j++ {if text1[i-1] == text2[j-1] {cur[j] = prev[j-1] + 1} else {cur[j] = max(prev[j], cur[j-1])}}copy(prev, cur)}return cur[m]}func max(a, b int) int {if a > b {return a}return b}
3、动态规划；时间复杂度O(n^2)，空间复杂度O(n)
func longestCommonSubsequence(text1 string, text2 string) int {n, m := len(text1), len(text2)cur := make([]int, m+1)for i := 1; i <= n; i++ {pre := cur[0]for j := 1; j <= m; j++ {temp := cur[j]if text1[i-1] == text2[j-1] {cur[j] = pre + 1} else {cur[j] = max(cur[j], cur[j-1])}pre = temp}}return cur[m]}func max(a, b int) int {if a > b {return a}return b}
03
—
总结
Medium题目，题目同leetcode 1143.最长公共子序列；类似的题目还有：
leetcode 583.两个字符串的删除操作；
leetcode 712.两个字符串的最小ASCII删除和；
leetcode 1035.不相交的线；
leetcode 1048.最长字符串链
本文来自网络或网友投稿，如有侵犯您的权益，请发邮件至：aisoutu@outlook.com 我们将第一时间删除。
相关素材