1143. Longest Common Subsequence

Medium

Description

給定兩個字串 text1 和 text2，回傳它們的最長公共子序列（LCS）的長度。子序列不需要連續但必須保持相對順序。若無公共子序列則回傳 0。

Example:

Input: text1 = “abcde”, text2 = “ace” Output: 3

Intuition#

比較兩個字串的字元：相同就從左上角 +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#

概念: 建立 (m+1) x (n+1) 的表格，逐格填寫 LCS 長度。
時間複雜度: O(m * n)
空間複雜度: 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（空間優化）#

概念: 用一維陣列加上一個變數 prev 保存 dp[i-1][j-1] 的值來滾動更新。
時間複雜度: O(m * n)
空間複雜度: 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] 表示兩個字串前綴的最優解
關鍵技巧: LCS 是許多字串 DP 問題的基礎（如 Edit Distance、Shortest Common Supersequence）；空間優化需要額外變數保存左上角值