給定兩個字符串?text1 和?text2，返回這兩個字符串的最長 公共子序列 的長度。如果不存在 公共子序列 ，返回 0 。

一個字符串的?子序列?是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
兩個字符串的 公共子序列 是這兩個字符串所共同擁有的子序列。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-common-subsequence
?

列：

輸入：text1 = "abcde", text2 = "ace" 輸出：3 解釋：最長公共子序列是 "ace" ，它的長度為 3 。

#解析：動態規劃，dp二維數組，每個字符串對應一維。對應的dp值后移一格，字符對上直接加一，對不上就繼承公共序列更長的一個。

class Solution(object):def longestCommonSubsequence(self, text1, text2):""":type text1: str:type text2: str:rtype: int"""len1, len2 = len(text1)+1, len(text2)+1 # 二維數組長寬dp = [[0 for i in range(len1)] for i in range(len2)] # 初始化數組for i in range(1, len2): # 行遍歷for j in range(1, len1): # 列遍歷if text1[j-1] == text2[i-1]: # 對應字符串相同的情況dp[i][j] = dp[i-1][j-1] +1 # 直接加一else:dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # 不同的情況取更長的一種情況return dp[-1][-1] # 返回右下角的值，即為最長公共子序列

總結

以上是生活随笔為你收集整理的最长公共子序列Python解法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。