Khoảng cách chỉnh sửa chuỗi Levenshtein (Edit Distance) DP

Mục tiêu kiến thức

• Xây dựng bảng quy hoạch động 2 chiều (M + 1) × (N + 1) tính khoảng cách Levenshtein.
• Tối ưu hóa các thao tác cơ bản: Chèn (Insert), Xóa (Delete), Thay thế (Substitute) và Giữ nguyên (Match).
• Lần vết (Backtracking) để xuất chuỗi thao tác biến đổi tối thiểu từ s1 thành s2.

Mô tả bài toán

Cho hai chuỗi ký tự s1 và s2. Bạn được phép thực hiện 3 thao tác trên s1:

• Chèn thêm 1 ký tự ("insert").
• Xóa 1 ký tự ("delete").
• Thay thế 1 ký tự bằng 1 ký tự khác ("substitute").

Viết hàm min_edit_distance(s1: str, s2: str) -> tuple[int, list[str]]:

• Tính số lượng thao tác ít nhất (Edit Distance) để chuyển đổi s1 thành s2.
• Tái dựng chuỗi thao tác biến đổi tối ưu: danh sách các chuỗi thao tác theo thứ tự từ đầu chuỗi đến cuối chuỗi, gồm các từ khóa:
• "keep": khi ký tự tại vị trí tương ứng giống nhau.
• "insert <char>": chèn ký tự <char> vào s1.
• "delete <char>": xóa ký tự <char> khỏi s1.
• "substitute <c1> -> <c2>": thay thế ký tự <c1> bằng <c2>.

Ưu tiên hòa điểm khi lần vết: ưu tiên keep/substitute trước, sau đó đến delete, cuối cùng đến insert.

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ả.