Chuỗi con chung dài nhất (Longest Common Subsequence) và Truy vết
Cho hai chuỗi text1 và text2. Một chuỗi con (subsequence) được tạo thành bằng cách xóa một số ký tự (hoặc không xóa) từ chuỗi ban đầu mà không làm thay đổi thứ tự các ký tự còn lại…
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: dp, strings.
Nội dung đề bài
Mục tiêu kiến thức
- Triển khai thuật toán quy hoạch động 2 chiều kinh điển cho bài toán LCS.
- Phân biệt rõ chuỗi con rời rạc (Subsequence) và xâu con liên tiếp (Substring).
- Lần vết bảng quy hoạch động để tái tạo chuỗi con chung dài nhất.
Mô tả bài toán
Cho hai chuỗi text1 và text2. Một chuỗi con (subsequence) được tạo thành bằng cách xóa một số ký tự (hoặc không xóa) từ chuỗi ban đầu mà không làm thay đổi thứ tự các ký tự còn lại.
Viết hàm longest_common_subsequence(text1: str, text2: str) -> tuple[int, str]:
- Trả về
(length, lcs_str). length: Độ dài của chuỗi con chung dài nhất giữatext1vàtext2.lcs_str: Chuỗi con chung dài nhất được tái tạo. Nếu có nhiều chuỗi cùng độ dài tối đa, ưu tiên chọn chuỗi theo quy tắc lần vết: nếu text1[i-1] == text2[j-1], chọn ký tự đó; nếu không, ưu tiên đi theo nhánh có dp[i-1][j] ≥ dp[i][j-1].- Nếu không có chuỗi con chung nào, trả về
(0, "").
Input
- Tham số:
text1: str,text2: str.
Output
- Trả về:
tuple[int, str].
Ràng buộc
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.
Ví dụ 1
Input
longest_common_subsequence('abcde', 'ace')Output
[3, 'ace']Giải thích
Hàm được gọi với các tham số mẫu trên và trả về kết quả chính xác theo yêu cầu.
Ví dụ 2
Input
longest_common_subsequence('abc', 'abc')Output
[3, 'abc']Giải thích
Hàm được gọi với bộ tham số thứ hai và trả về kết quả tương ứng theo thiết kế.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.