溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
