小编给大家分享一下leetcode如何求最长公共子序列,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列,则返回 0。
示例 1:输入:text1 = "abcde", text2 = "ace" 输出:3 解释:最长公共子序列是 "ace",它的长度为 3。示例 2:输入:text1 = "abc", text2 = "abc"输出:3解释:最长公共子序列是 "abc",它的长度为 3。示例 3:输入:text1 = "abc", text2 = "def"输出:0解释:两个字符串没有公共子序列,返回 0。
提示:
1 <= text1.length <= 1000
1 <= text2.length <= 1000
输入的字符串只含有小写英文字符。
解题思路:
1,注意是最长公共子序列,不是最长公共子串
2,最长公共子序列问题是经典的动态规划题
3,状态转移方程
A,若str1[i]==str2[j],则str1[:i]和str2[:j]最长公共子序列的长度为
str1[:i-1]和str2[:j-1]最长公共子序列的长度加一
B, str1[:i-1]和str2[:j], str1[:i]和str2[:j-1]两者中较长者
4,未来表示方便,存储数组长度比字符串长度多1
代码实现
func longestCommonSubsequence(text1 string, text2 string) int { h:=len(text1)+1 w:=len(text2)+1 m:=make([][]int,h) for i:=0;i<h;i++{ m[i]=make([]int,w) } for i:=1;i<h;i++{ for j:=1;j<w;j++{ if text1[i-1]==text2[j-1]{ m[i][j]=m[i-1][j-1]+1 }else{ if m[i-1][j]>m[i][j-1]{ m[i][j]=m[i-1][j] }else{ m[i][j]=m[i][j-1] } } } } return m[h-1][w-1]}
以上是“leetcode如何求最长公共子序列”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/4586289/blog/4404227