給定兩個字串
text1和text2，回傳它們的最長公共子序列（LCS）的長度。子序列不需要連續但必須保持相對順序。若無公共子序列則回傳 0。
Example:
Input: text1 = “abcde”, text2 = “ace” Output: 3
Intuition
TIP
比較兩個字串的字元：相同就從左上角 +1，不同就取上方或左方的最大值。
dp[i][j]代表text1[0..i-1]和text2[0..j-1]的 LCS 長度- 若
text1[i-1] == text2[j-1]，則dp[i][j] = dp[i-1][j-1] + 1 - 否則
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Approaches
1. 2D DP Table — O(m * n) / O(m * n)
- Idea: 建立
(m+1) x (n+1)的表格，逐格填寫 LCS 長度。 - Time:
O(m * n) - Space:
O(m * n)
class Solution {
fun longestCommonSubsequence(text1: String, text2: String): Int {
val m = text1.length
val n = text2.length
val dp = Array(m + 1) { IntArray(n + 1) }
for (i in 1..m) {
for (j in 1..n) {
dp[i][j] = if (text1[i - 1] == text2[j - 1]) {
dp[i - 1][j - 1] + 1
} else {
maxOf(dp[i - 1][j], dp[i][j - 1])
}
}
}
return dp[m][n]
}
}⭐ 2. 1D DP (Space Optimized) — O(m * n) / O(n)
- Idea: 用一維陣列加上一個變數
prev保存dp[i-1][j-1]的值來滾動更新。 - Time:
O(m * n) - Space:
O(n)
class Solution {
fun longestCommonSubsequence(text1: String, text2: String): Int {
val m = text1.length
val n = text2.length
val dp = IntArray(n + 1)
for (i in 1..m) {
var prev = 0
for (j in 1..n) {
val temp = dp[j]
dp[j] = if (text1[i - 1] == text2[j - 1]) {
prev + 1
} else {
maxOf(dp[j], dp[j - 1])
}
prev = temp
}
}
return dp[n]
}
}🔑 Takeaways
- Pattern: 雙字串 DP —
dp[i][j]表示兩個字串前綴的最優解 - Key trick: LCS 是許多字串 DP 問題的基礎（如 Edit Distance、Shortest Common Supersequence）；空間優化需要額外變數保存左上角值