Longest Common Subsequence

Q: Độ phức tạp thời gian của dãy con chung dài nhất là bao nhiêu?

Lời giải bằng bảng chạy trong thời gian O(n × m) , mỗi cặp tiền tố ứng với một ô. Cách này cần O(n × m) bộ nhớ cho toàn bộ bảng, hoặc O(min(n, m)) nếu dùng hai hàng. Đệ quy thông thường không dùng bảng có độ phức tạp theo hàm mũ.

Trung bìnhQuy hoạch động

+10

Bạn nhận được hai chuỗi, text1 và text2. Chuỗi con của một chuỗi giữ lại một số ký tự theo đúng thứ tự ban đầu và bỏ những ký tự còn lại; các ký tự được giữ lại không nhất thiết phải đứng cạnh nhau. Hãy trả về độ dài của chuỗi dài nhất là chuỗi con của cả hai chuỗi, hoặc 0 nếu hai chuỗi không có ký tự nào chung.

Hàm

longestCommonSubsequence(text1: string, text2: string) → integer

text1string: chuỗi đầu tiên
text2string: chuỗi thứ hai
Trả vềinteger: độ dài của dãy con chung dài nhất

Ràng buộc

1 ≤ text1.length ≤ 1000
1 ≤ text2.length ≤ 1000
Cả hai chuỗi chỉ chứa các chữ cái tiếng Anh viết thường.

Ví dụ

Đầu vào: text1 = "stone"text2 = "longest"
Đầu ra: 3
Giải thích: o, n, e xuất hiện theo thứ tự này trong cả hai từ, nên one là phần chung, có độ dài 3. Các chữ cái s và t đứng cuối trong longest nhưng đứng đầu trong stone, nên dùng chúng thì phần chung dài nhất là st.

Đầu vào: text1 = "pear"text2 = "reap"
Đầu ra: 2
Giải thích: ea xuất hiện trong cả hai từ. Chữ p và chữ r nằm ở hai phía đối diện của ea trong hai từ, nên không chữ nào có thể ghép với nó, và đáp án là 2.

Câu hỏi mở rộng

Bạn có thể trả về một dãy con chung dài nhất, cùng với độ dài của nó không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Khớp tham lam không thành công: ghép ký tự c trong cab với ký tự c cuối cùng trong abc khiến không còn gì cho a và b; bỏ qua ký tự đó sẽ tìm được ab. Đáp án cho hai tiền tố phụ thuộc vào đáp án của các tiền tố ngắn hơn, vì vậy một bảng (n+1) × (m+1) giải từng cặp đúng một lần. Mỗi hàng chỉ đọc hàng phía trên, nên hai hàng là đủ.

So sánh chữ cái đầu tiên bằng đệ quy

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Gọi lcs(i, j) là đáp án cho các hậu tố text1[i:] và text2[j:]. Nếu chữ cái đầu tiên của chúng giống nhau, hãy ghép chúng lại: một dãy con chung dài nhất bỏ qua cặp này có thể thay cặp đầu tiên bằng cặp này mà không bị ngắn hơn. Vì vậy, đáp án là 1 + lcs(i+1, j+1).

Nếu các chữ cái khác nhau, không thể dùng cả hai, vì các chữ ghép với chúng sẽ khiến các cặp giao nhau. Vì vậy, có thể bỏ một trong hai: max(lcs(i+1, j), lcs(i, j+1)). Hậu tố rỗng có giá trị 0.

Mỗi chỗ không khớp bắt đầu hai lần gọi. Hai chuỗi gồm 20 chữ cái không có chữ cái chung đã cần khoảng 2.8 × 10^11 lần gọi, trong khi chỉ có (n+1) × (m+1) cặp khác nhau (i, j), nên gần như mọi lần gọi đều lặp lại một lần gọi trước đó.

Thuật toán

Viết lcs(i, j) cho các hậu tố bắt đầu tại i và j.
Nếu i hoặc j vượt quá cuối chuỗi tương ứng, trả về 0.
Nếu text1[i] == text2[j], trả về 1 + lcs(i+1, j+1).
Nếu không, trả về max(lcs(i+1, j), lcs(i, j+1)).
Đáp án là lcs(0, 0).

def longestCommonSubsequence(text1, text2):
    def lcs(i, j):
        # The longest common subsequence of text1[i:] and text2[j:]
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + lcs(i + 1, j + 1)
        return max(lcs(i + 1, j), lcs(i, j + 1))

    return lcs(0, 0)

Điền vào bảng tiền tố

Ý tưởng

Gọi dp[i][j] là đáp án cho i chữ cái đầu tiên của text1 và j chữ cái đầu tiên của text2, vì vậy chỉ số 0 nghĩa là tiền tố rỗng, hàng 0 và cột 0 đều bằng 0. So sánh chữ cái cuối của hai tiền tố, text1[i-1] và text2[j-1]: nếu hai chữ cái giống nhau, ghép chúng lại, dp[i-1][j-1] + 1; nếu khác nhau, bỏ một trong hai, max(dp[i-1][j], dp[i][j-1]). Đây là công thức đệ quy được đọc từ cuối.

Mỗi ô đọc các ô phía trên, bên trái và chéo lên trên bên trái, vì vậy điền từng hàng từ trái sang phải sẽ luôn có sẵn các ô đó. Với pear và reap, hàng ứng với pea là [0, 0, 1, 2, 2]; ô ứng với rea có giá trị 2 vì a khớp với a, cộng thêm một vào ô ứng với pe và re.

Hai chuỗi có 1000 chữ cái cần khoảng 10^6 bước có thời gian không đổi.

Thuật toán

Tạo một bảng dp gồm (n+1) × (m+1) số 0.
Với i từ 1 đến n và j từ 1 đến m, hãy so sánh text1[i-1] với text2[j-1].
Nếu khớp, đặt dp[i][j] = dp[i-1][j-1] + 1.
Nếu không, đặt dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Trả về dp[n][m].

def longestCommonSubsequence(text1, text2):
    n, m = len(text1), len(text2)
    # dp[i][j]: the longest common subsequence of text1[:i] and text2[:j].
    # Row 0 and column 0 stay 0: an empty prefix has nothing in common.
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Chỉ giữ lại hai hàng

Ý tưởng

Khi hoàn thành một hàng, bạn không bao giờ đọc lại các hàng phía trên hàng đó. Giữ prev cho hàng đã hoàn thành và cur cho hàng đang được điền, rồi đổi chỗ chúng sau mỗi hàng. Công thức truy hồi và thứ tự vẫn giữ nguyên.

Đáp án không phụ thuộc vào chuỗi nào đứng trước, vì vậy hãy để các hàng chạy dọc theo chuỗi ngắn hơn. Khi đó, mỗi hàng chỉ chứa min(n, m) + 1 số: 1001 thay vì một triệu ô với các đầu vào lớn nhất, trong khi vẫn cần 10^6 bước.

Thuật toán

Nếu text2 dài hơn text1, hãy đổi chỗ chúng.
Tạo prev và cur, mỗi biến có m + 1 giá trị 0, trong đó m là độ dài ngắn hơn.
Với mỗi ký tự trong text1, điền cur[1..m] theo cùng quy tắc như trong bảng, đọc giá trị từ prev ở hàng phía trên.
Đổi chỗ prev và cur.
Trả về prev[m].

def longestCommonSubsequence(text1, text2):
    if len(text2) > len(text1):
        text1, text2 = text2, text1  # keep the rows as short as the shorter string
    m = len(text2)
    # prev[j]: the answer for the previous prefix of text1 and text2[:j]
    prev = [0] * (m + 1)
    for ch in text1:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if ch == text2[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

Lỗi thường gặp và trường hợp biên

Nhầm chỉ số của bảng với chỉ số chuỗi. Ô dp[i][j] so sánh text1[i-1] với text2[j-1], vì hàng 0 là tiền tố rỗng.
Khi khớp, cộng một vào max(dp[i-1][j], dp[i][j-1]) thay vì dp[i-1][j-1]. Cách đó có thể dùng một chữ cái hai lần: aa so với a sẽ trả về 2 thay vì 1.
Ghi vào hàng mà bạn vẫn đang đọc. Khi dùng hai hàng, mọi giá trị từ hàng phía trên phải lấy từ prev, và cur[0] phải luôn là 0.
Ghi nhớ kết quả đệ quy trong Python với chuỗi dài 1000 ký tự. Độ sâu lời gọi đạt 2000, vượt quá giới hạn mặc định là 1000.

Câu hỏi thường gặp3

Độ phức tạp thời gian của dãy con chung dài nhất là bao nhiêu?

Lời giải bằng bảng chạy trong thời gian O(n × m), mỗi cặp tiền tố ứng với một ô. Cách này cần O(n × m) bộ nhớ cho toàn bộ bảng, hoặc O(min(n, m)) nếu dùng hai hàng. Đệ quy thông thường không dùng bảng có độ phức tạp theo hàm mũ.

Sự khác biệt giữa dãy con chung dài nhất và chuỗi con chung dài nhất là gì?

Dãy con có thể bỏ qua các chữ cái miễn là vẫn giữ nguyên thứ tự; chuỗi con là một khối gồm các chữ cái liền kề. Với stone và longest, dãy con chung dài nhất là one (3), còn chuỗi con chung dài nhất là on (2). Bảng chuỗi con đặt lại ô thành 0 khi các ký tự không khớp, thay vì sao chép giá trị từ ô bên cạnh.

LCS liên quan thế nào đến các công cụ so sánh khác biệt và khoảng cách chỉnh sửa?

Bản diff giữa hai phiên bản của một tệp giữ lại dãy con chung dài nhất gồm các dòng và hiển thị mọi dòng khác dưới dạng được thêm vào hoặc bị xóa. Số lần chèn và xóa ít nhất để biến chuỗi này thành chuỗi kia là n + m - 2 × LCS. Khoảng cách chỉnh sửa cũng cho phép thay thế một chữ cái, nên cần một bảng riêng.

def longestCommonSubsequence(text1, text2):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

text1 = "stone"
text2 = "longest"

Đầu ra mong đợi

Longest Common Subsequence

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

So sánh chữ cái đầu tiên bằng đệ quy

Điền vào bảng tiền tố

Chỉ giữ lại hai hàng

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự