Longest Common Subsequence

題目描述

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

輸入：text1 = "abcde", text2 = "ace"
輸出：3
解釋：LCS 是 "ace"

輸入：text1 = "abc", text2 = "def"
輸出：0

解題思路

定義狀態

dp[i][j] = text1 前 i 個字元和 text2 前 j 個字元的 LCS 長度。dp[0][j] = dp[i][0] = 0（空字串的 LCS 為 0）

字元相同

text1[i-1] == text2[j-1] 時，這對字元加入 LCS：dp[i][j] = dp[i-1][j-1] + 1。例如 text1=ace, text2=ace → dp[1][1] = dp[0][0]+1 = 1

字元不同

text1[i-1] != text2[j-1] 時，這對字元無法同時使用：dp[i][j] = max(dp[i-1][j], dp[i][j-1])，取跳過 text1 或跳過 text2 的較大值

填表方向

從左上到右下逐格填表，保證計算 dp[i][j] 時其依賴的三個格子都已填好

答案

dp[m][n] 即為 text1 和 text2 的完整 LCS 長度

程式碼

C#

csharp

public class Solution {
    public int LongestCommonSubsequence(string text1, string text2) {
        int m = text1.Length, n = text2.Length;
        // 空間優化：只用一維陣列
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= m; i++) {
            int prev = 0; // dp[i-1][j-1]
            for (int j = 1; j <= n; j++) {
                int temp = dp[j]; // 暫存 dp[i-1][j]
                if (text1[i - 1] == text2[j - 1]) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.Max(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }
        return dp[n];
    }
}

TypeScript

typescript

function longestCommonSubsequence(text1: string, text2: string): number {
    const m = text1.length, n = text2.length;
    const dp: number[][] = Array.from({length: m + 1}, () => new Array(n + 1).fill(0));
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[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];
}

Python

python

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    # 空間優化版本
    dp = [0] * (n + 1)
    
    for i in range(1, m + 1):
        prev = 0
        for j in range(1, n + 1):
            temp = dp[j]
            if text1[i - 1] == text2[j - 1]:
                dp[j] = prev + 1
            else:
                dp[j] = max(dp[j], dp[j - 1])
            prev = temp
    
    return dp[n]

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(m × n) | O(n)（空間優化後） |

Time：填一個 (m+1)×(n+1) 的表格，每格 O(1) 操作
Space：空間優化用一維陣列長度 n+1，加一個 prev 暫存變數

圖解

dp 表格 (m+1)×(n+1)

text1[i]==text2[j]→

字元相同 → 左上+1

填表→

字元不同 → max(上,左)

填表→

dp[m][n] = LCS 長度

圖表展示了 DP 的兩條轉移路徑：字元匹配走「左上角 +1」，不匹配走「上方或左方取 max」。每格只依賴左上、上方、左方三個值，所以可以用一維陣列加一個 prev 暫存變數來空間優化。

進階觀點

💡面試追問

如何輸出實際的 LCS 字串？ 保留完整的 2D dp 表格，從 dp[m][n] 開始反向追溯：字元相同時加入結果並走左上，不同時走上方或左方中值較大的。最後反轉字串得到 LCS。
和 583. Delete Operation 的關係？ 兩個字串的最少刪除次數 = m + n - 2 × LCS。因為 LCS 是兩者共有的部分，其餘字元都要刪掉。
和 72. Edit Distance 的關係？ Edit Distance 在 LCS 基礎上增加「替換」操作。LCS 只考慮保留和跳過，Edit Distance 多了一種「把 text1[i] 改成 text2[j]」的選項。
實際應用？ diff 工具（比較兩個檔案的差異）、Git 版本控制（merge conflict 解析）、DNA 序列比對（Bioinformatics）都以 LCS 為核心演算法。

邊界情況

其中一個字串為空：LCS 長度為 0，dp 表格第一行和第一列全為 0
兩個字串完全相同：LCS 就是字串本身，長度等於字串長度
兩個字串沒有任何公共字元：LCS 長度為 0，dp 表格內部全為 0

理解測驗

🤔 為什麼字元相同時是 dp[i-1][j-1]+1 而不是 dp[i-1][j]+1？

🤔 LCS 的「子序列」和「子字串」有什麼區別？