Longest Common Subsequence

Bài toán

Cho hai chuỗi text1 và text2. Tìm độ dài dãy con chung dài nhất của chúng. Dãy con chung: là dãy con của cả hai chuỗi (giữ nguyên thứ tự tương đối).

Ví dụ:

text1 = "abcde", text2 = "ace" 
Output: 3 ("ace")

Phân Tích & Tiếp Cận

2D DP Table

Gọi dp[i][j] là độ dài LCS của text1[0...i-1] và text2[0...j-1]. Ta cần bảng kích thước (n+1) x (m+1).

Tại mỗi cặp ký tự text1[i] và text2[j]:

1. Nếu ký tự giống nhau (text1[i] == text2[j]):
   • Ta chắc chắn lấy ký tự này vào dãy con chung.
   • Điểm cộng thêm 1 + kết quả của phần trước đó (chéo trên).
   • dp[i][j] = 1 + dp[i-1][j-1].
2. Nếu ký tự khác nhau:
   • Ta không thể lấy cả hai cùng lúc được. Ta thử bỏ 1 trong 2 và lấy cái max.
   • dp[i][j] = max(dp[i-1][j], dp[i][j-1]). (Lấy max của ô bên trên và ô bên trái).

function longestCommonSubsequence(text1: string, text2: string): number {
    const n = text1.length;
    const m = text2.length;
    const dp = Array(n + 1).fill(0).map(() => Array(m + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[n][m];
}

• Time Complexity: $O(n \cdot m)$.
• Space Complexity: $O(n \cdot m)$.

Pattern Nhận Diện

• So sánh sự tương đồng giữa 2 chuỗi.
• Diff tool, gene sequencing.
• Hai con trỏ trên 2 chuỗi -> mở rộng thành bảng 2 chiều.