写点什么

[Day8]-[动态规划] 最长公共子序列

作者:方勇(gopher)
  • 2022 年 4 月 07 日
  • 本文字数:706 字

    阅读完需:约 2 分钟

[Day8]-[动态规划] 最长公共子序列

1143. 最长公共子序列

难度中等 925 收藏分享切换为英文接收动态反馈

给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

  • 例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

 

示例 1:

输入:text1 = "abcde", text2 = "ace" 输出:3  解释:最长公共子序列是 "ace" ,它的长度为 3 。
复制代码

示例 2:

输入:text1 = "abc", text2 = "abc"输出:3解释:最长公共子序列是 "abc" ,它的长度为 3 。
复制代码

示例 3:

输入:text1 = "abc", text2 = "def"输出:0解释:两个字符串没有公共子序列,返回 0 。
复制代码


题解:

func longestCommonSubsequence(text1 string, text2 string) int {	var solution func(str1, str2 string) int	var max func(x, y int) int	max = func(x, y int) int {		if x > y {			return x		}		return y	}	solution = func(str1, str2 string) int {		m, n := len(str1), len(str2)		var dp = make([][]int, m+1)		for i := 0; i <= m; i++ {			dp[i] = make([]int, n+1)		}		for i := 1; i <= m; i++ {			for j := 1; j <= n; j++ {				if str1[i-1] == str2[j-1] {					dp[i][j] = dp[i-1][j-1] + 1 // 取对角线+1				} else {					dp[i][j] = max(dp[i][j-1], dp[i-1][j]) // 取左边 或 上边 最大值				}			}		}
return dp[m][n] }
return solution(text1, text2)}
复制代码


用户头像

Dead or Alive. 生存战斗是知识的源泉! 2018.11.08 加入

我是一名SRE哨兵,目前是好大夫基础架构部高级工程师。专注于 SRE,微服务、中间件的稳定性和可用性建设,整体负责好大夫服务治理云平台的设计和搭建!

评论

发布
暂无评论
[Day8]-[动态规划] 最长公共子序列_LeetCode_方勇(gopher)_InfoQ写作平台