網(wǎng)站怎么做可以再上面輸入文字百度搜題
LeetCode-1143. 最長公共子序列【字符串 動(dòng)態(tài)規(guī)劃】
- 題目描述:
- 解題思路一:動(dòng)規(guī)五部曲
- 解題思路二:1維DP
- 解題思路三:0
題目描述:
給定兩個(gè)字符串 text1 和 text2,返回這兩個(gè)字符串的最長 公共子序列 的長度。如果不存在 公共子序列 ,返回 0 。
一個(gè)字符串的 子序列 是指這樣一個(gè)新的字符串:它是由原字符串在不改變字符的相對(duì)順序的情況下刪除某些字符(也可以不刪除任何字符)后組成的新字符串。
例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。
兩個(gè)字符串的 公共子序列 是這兩個(gè)字符串所共同擁有的子序列。
示例 1:
輸入:text1 = “abcde”, text2 = “ace”
輸出:3
解釋:最長公共子序列是 “ace” ,它的長度為 3 。
示例 2:
輸入:text1 = “abc”, text2 = “abc”
輸出:3
解釋:最長公共子序列是 “abc” ,它的長度為 3 。
示例 3:
輸入:text1 = “abc”, text2 = “def”
輸出:0
解釋:兩個(gè)字符串沒有公共子序列,返回 0 。
提示:
1 <= text1.length, text2.length <= 1000
text1 和 text2 僅由小寫英文字符組成。
解題思路一:動(dòng)規(guī)五部曲
- 確定dp數(shù)組(dp table)以及下標(biāo)的含義
dp[i][j]:長度為[0, i - 1]的字符串text1與長度為[0, j - 1]的字符串text2的最長公共子序列為dp[i][j]
有同學(xué)會(huì)問:為什么要定義長度為[0, i - 1]的字符串text1,定義為長度為[0, i]的字符串text1不香么?
這樣定義是為了后面代碼實(shí)現(xiàn)方便,如果非要定義為長度為[0, i]的字符串text1也可以,我在 動(dòng)態(tài)規(guī)劃:718. 最長重復(fù)子數(shù)組 (opens new window)中的「拓展」里 詳細(xì)講解了區(qū)別所在,其實(shí)就是簡化了dp數(shù)組第一行和第一列的初始化邏輯。
- 確定遞推公式
主要就是兩大情況: text1[i - 1] 與 text2[j - 1]相同,text1[i - 1] 與 text2[j - 1]不相同
如果text1[i - 1] 與 text2[j - 1]相同,那么找到了一個(gè)公共元素,所以dp[i][j] = dp[i - 1][j - 1] + 1;
如果text1[i - 1] 與 text2[j - 1]不相同,那就看看text1[0, i - 2]與text2[0, j - 1]的最長公共子序列 和 text1[0, i - 1]與text2[0, j - 2]的最長公共子序列,取最大的。
即:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
- dp數(shù)組如何初始化
先看看dp[i][0]應(yīng)該是多少呢?
test1[0, i-1]和空串的最長公共子序列自然是0,所以dp[i][0] = 0;
同理dp[0][j]也是0。
其他下標(biāo)都是隨著遞推公式逐步覆蓋,初始為多少都可以,那么就統(tǒng)一初始為0。
-
確定遍歷順序
從遞推公式,可以看出,有三個(gè)方向可以推出dp[i][j],如圖:
那么為了在遞推的過程中,這三個(gè)方向都是經(jīng)過計(jì)算的數(shù)值,所以要從前向后,從上到下來遍歷這個(gè)矩陣。
-
舉例推導(dǎo)dp數(shù)組
以輸入:text1 = “abcde”, text2 = “ace” 為例,dp狀態(tài)如圖:
最后紅框dp[text1.size()][text2.size()]為最終結(jié)果
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:# 創(chuàng)建一個(gè)二維數(shù)組 dp,用于存儲(chǔ)最長公共子序列的長度dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]# 遍歷 text1 和 text2,填充 dp 數(shù)組for i in range(1, len(text1) + 1):for j in range(1, len(text2) + 1):if text1[i - 1] == text2[j - 1]:# 如果 text1[i-1] 和 text2[j-1] 相等,則當(dāng)前位置的最長公共子序列長度為左上角位置的值加一dp[i][j] = dp[i - 1][j - 1] + 1else:# 如果 text1[i-1] 和 text2[j-1] 不相等,則當(dāng)前位置的最長公共子序列長度為上方或左方的較大值dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])# 返回最長公共子序列的長度return dp[len(text1)][len(text2)]# 同意
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:m, n = len(text1), len(text2)dp = [[0] * (n+1) for _ in range(m+1)]for i in range(1, m+1):for j in range(1, n+1):if text1[i-1] != text2[j-1]:dp[i][j] = max(dp[i-1][j], dp[i][j-1])else:dp[i][j] = dp[i-1][j-1] + 1return dp[-1][-1]
時(shí)間復(fù)雜度:O(nm)
空間復(fù)雜度:O(nm)
解題思路二:1維DP
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:m, n = len(text1), len(text2)dp = [0] * (n + 1) # 初始化一維DP數(shù)組for i in range(1, m + 1):prev = 0 # 保存上一個(gè)位置的最長公共子序列長度for j in range(1, n + 1):curr = dp[j] # 保存當(dāng)前位置的最長公共子序列長度if text1[i - 1] == text2[j - 1]:# 如果當(dāng)前字符相等,則最長公共子序列長度加一dp[j] = prev + 1else:# 如果當(dāng)前字符不相等,則選擇保留前一個(gè)位置的最長公共子序列長度中的較大值dp[j] = max(dp[j], dp[j - 1])prev = curr # 更新上一個(gè)位置的最長公共子序列長度return dp[n] # 返回最后一個(gè)位置的最長公共子序列長度作為結(jié)果
時(shí)間復(fù)雜度:O(nm)
空間復(fù)雜度:O(n)
解題思路三:0
時(shí)間復(fù)雜度:O(n)
空間復(fù)雜度:O(n)