小编给大家分享一下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)+1w:=len(text2)+1m:=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如何求最长公共子序列”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
