Re: [閒聊] 每日LeetCode
1143. Longest Common Subsequence
給你兩個字串求出它們的最長共通子序列長。
Example：
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
思路：
1.這題是演算法課程有教dp都會提到的經典題目，大多子字串問題也多是用dp解。
2.先定義dp，dp[i][j] 表示s1長度為i 且 s2長度為j時的最長子序列長度，所以我們
宣告一個大小為dp[m+1][n+1]的陣列（因為要包含長度為0的case）
3.再來我們需要找出狀態轉移方程式，字串s1和s2的最後一個元素分別以e1與e2
表示，剩餘部分以 sub1 與 sub2表示，故可以將其如下表示：
s1 = sub1 + e1
s2 = sub2 + e2
可以分成四個情形討論：
LCS包含e1不包含e2
LCS(s1,s2) = LCS(s1,sub2) // 捨棄右邊
LCS包含e2不包含e1
LCS(s1,s2) = LCS(sub1,s2) // 捨棄左邊
LCS包含e1且包含e2
LCS(s1,s2) = LCS(sub1,sub2) + 1 // 全捨棄且序列長度加一
LCS不包含e1且不包含e2
LCS(s1,s2) = LCS(sub1,sub2) // 全捨棄
上述四個式子可以結論如下：
LCS(s1,s2) = max(LCS(s1,sub2), LCS(sub1,s2), LCS(sub1,sub2)) when e1 ≠ e2
LCS(sub1, sub2) + 1 when e1 == e2
因為都不取一定比只取一個小，所以全捨棄的case可以無視，有了遞迴關係式就可以
改寫成迭代，表示如下：
dp[i][j] = dp[i-1][j-1] when s[i]==s[j]
max(dp[i-1][j], dp[i][j-1]) when s[i]!=s[j]
Java Code：
--------------------------------
class Solution {
public int longestCommonSubsequence(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
--------------------------------
另外，這題一樣可以空間複雜度優化，因為我們只需要上一行的值和左邊的值所以
只需要一個大小為[n][2]的陣列，其中一個陣列暫存上一行的值，空間複雜度
O(mn) => O(n)
Java Code：
--------------------------------
class Solution {
public int longestCommonSubsequence(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int[] dp = new int[n + 1];
int[] tmp = new int[n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[j] = tmp[j - 1] + 1;
} else {
dp[j] = Math.max(tmp[j], dp[j - 1]);
}
}
for (int j = 1; j <= n;j++) {
tmp[j] = dp[j];
}
}
return dp[n];
}
}
--------------------------------
今天好冷 好想回家睡覺==
--
https://i.imgur.com/sjdGOE3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.89.30 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671073168.A.02E.html
推
12/15 11:00,
3年前
, 1F
12/15 11:00, 1F
→
12/15 11:00,
3年前
, 2F
12/15 11:00, 2F
→
12/15 11:01,
3年前
, 3F
12/15 11:01, 3F
推
12/15 11:02,
3年前
, 4F
12/15 11:02, 4F
→
12/15 11:04,
3年前
, 5F
12/15 11:04, 5F
討論串 (同標題文章)
完整討論串 (本文為第 137 之 719 篇)：