Cách Tìm Chuỗi Con Chung Dài Nhất Giữa Hai Chuỗi Trong JavaScript

Để tìm chuỗi con chung dài nhất giữa hai chuỗi trong JavaScript, bạn có thể sử dụng thuật toán Dynamic Programming. Thuật toán này giúp tối ưu hóa việc tìm kiếm chuỗi con chung bằng cách lưu trữ kết quả của các bài toán con để tránh tính toán lại nhiều lần.

Mã Nguồn:

function longestCommonSubsequence(str1, str2) {
    let m = str1.length;
    let n = str2.length;
    
    // Tạo bảng lưu trữ độ dài của chuỗi con chung dài nhất
    let dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    // Xây dựng bảng dp từ dưới lên
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (str1[i - 1] === str2[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]);
            }
        }
    }

    // Tạo chuỗi con chung dài nhất từ bảng dp
    let lcs = '';
    let i = m, j = n;
    while (i > 0 && j > 0) {
        if (str1[i - 1] === str2[j - 1]) {
            lcs = str1[i - 1] + lcs;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    return lcs;
}

// Ví dụ kiểm tra
console.log(longestCommonSubsequence("ABCBDAB", "BDCAB")); // "BCAB"

Giải Thích:

1. Tạo Bảng DP:

   • dp[i][j]: Đại diện cho độ dài của chuỗi con chung dài nhất của str1[0...i-1] và str2[0...j-1].

2. Điền Bảng DP:

   • Nếu ký tự hiện tại của str1 và str2 giống nhau, tăng độ dài chuỗi con chung bằng giá trị của dp[i-1][j-1] cộng thêm 1.
   • Nếu khác nhau, chọn giá trị lớn hơn giữa dp[i-1][j] và dp[i][j-1].

3. Xây Dựng Chuỗi Con Chung Dài Nhất:

   • Bắt đầu từ góc dưới bên phải của bảng và quay ngược lại để xây dựng chuỗi con chung dài nhất từ kết quả.

Tổng Quan:

• Chuỗi Con Chung Dài Nhất (LCS): Là chuỗi con dài nhất xuất hiện trong cả hai chuỗi.
• Thuật Toán DP: Hiệu quả trong việc giải quyết bài toán tối ưu hóa bằng cách lưu trữ kết quả trung gian.
• Ứng Dụng: Cơ bản trong các bài toán so sánh chuỗi và phân tích dữ liệu.

Ví Dụ Thực Tế:

console.log(longestCommonSubsequence("ABCBDAB", "BDCAB")); // "BCAB"

Trong ví dụ trên, chuỗi con chung dài nhất của "ABCBDAB" và "BDCAB" là "BCAB".