Problem: 1143. 最長公共子序列

題目描述

思路

我們統一標記：str1[i]代表text1表示的字符數組，str2[j]代表text2表示的字符數組；LCS代表最長的公共子序列；（我們易得只有str1[i]和str2[j]均在LCS中時才能說明str1[i]和str2[j]是LCS的一部分）

1.狀態定義：dp[i][j]代表str1[1~i]和str2[1 ~ j]的最長公共子序列（我們暫時認為索引是從 1 開始的，例如：d[2][4] 的含義就是：對于 “ac” 和 “babc” ，它們的LCS ?度是 2）

2.狀態轉移：

2.1:初始狀態初始化：我們初始化dp[0][j] = 0; dp[i][0] = 0,邏輯上說明，當str1或者str2其中為空時則LCS為0；
2.2:狀態轉移：若*str1[i] == str2[j]則dp[i][j] = dp[i - 1][j - 1] + 1;若str1[i] != str2[j]*則dp[i][j] == max(dp[i-1][j],dp[i][j-1])

補充：

當*str1[i] != str2[j]*實則有三種狀態：str1[i] != LCS[i];str2[j] != LCS[j]; str1[i] != str2[i] != LCS[i];但是我們在狀態轉移方程中dp[i][j] == max(dp[i-1][j],dp[i][j-1]);
實際上dp[i][j] == max(dp[i-1][j],dp[i][j-1]，dp[i - 1][j - 1]),但是回看dp[i][j]的定義我們易知dp[i - 1][j - 1]是一定小于dp[i-1][j]和dp[i][j-1],所以我們則直接求取**max(dp[i-1][j],dp[i][j-1])**即可

復雜度

時間復雜度:

$O(M\times N)$;其中$M$為text1的長度，$N$為text2的長度

空間復雜度:

$O(M\times N)$

Code

class Solution {
public:/*** Find the longest common subsequence* @param text1 Given string* @param text2 Given string* @return int*/int longestCommonSubsequence(string text1, string text2) {int len1 = text1.length();int len2 = text2.length();//DP arrayvector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1));//for (int i = 1; i < len1 + 1; ++i) {for (int j = 1; j < len2 + 1; ++j) {if (text1.at(i - 1) == text2.at(j - 1)) {dp[i][j] = 1 + dp[i - 1][j - 1];} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[len1][len2];}
};