1 題目描述

2 解題思路

我們可以用動態規劃解決這個問題。

假設我們用坐標i表示當前遍歷到的text1的坐標，j表示當前遍歷到的text2的坐標。ret[i][j]表示text1遍歷到i，text2遍歷到j的時候的最長公共子序列長度。

?

那么對每一對(i,j),ret[i][j]滿足：

·如果text1[i]=text2[j]，那么ret[i][j]是ret[i][j-1]（text1的i坐標和text2的j-1坐標匹配）、ret[i-1][j]（text1的i-1坐標和text2的j坐標匹配）、ret[i-1][j-1]+1（text1的i-1坐標和text2的j-1坐標匹配）中最大的一個。

·如果text1[i]≠text2[j]，那么ret[i][j]是ret[i][j-1]（text1的i坐標和text2的j-1坐標匹配）、ret[i-1][j]（text1的i-1坐標和text2的j坐標匹配）、ret[i-1][j-1]（text1的i-1坐標和text2的j-1坐標匹配）中最大的一個。

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:ret=[]for i in range(len(text1)+1):ret.append([0]*(len(text2)+1))for i in range(1,len(text1)+1):for j in range(1,len(text2)+1):ret[i][j]=max(ret[i][j-1],ret[i-1][j],ret[i-1][j-1]+(text1[i-1]==text2[j-1]))return(max(max(ret)))

?

總結

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

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