Mini-challenge Edit Distance có trọng số: chi phí sửa không đối xứng

Bài 03 cho edit distance với mọi phép giá 1. Thực tế thì không phép nào ngang giá nhau. Bàn phím hay gõ thiếu chữ hơn gõ thừa chữ, nên autocorrect coi "thiếu một ký tự" rẻ hơn "thừa một ký tự". diff tính thay một dòng bằng dòng khác là hai việc (xoá rồi thêm), không phải một. Sinh học thì cho mỗi cặp base thay nhau một mức phạt riêng. Tất cả đều là cùng một bảng DP, chỉ khác ba con số.

Thử thách này đổi ba con số đó thành tham số. Đề nghe gần như bài 03, nhưng lời giải cũ chép lại sẽ sai ở hai chỗ mà test vector bên dưới được chọn để bắt.

Dành 20 đến 25 phút tự cài đặt trước khi xem gợi ý. Chưa quen mổ xẻ đề bài thì ôn lại đọc đề bài trước khi viết dòng code đầu tiên.

Đề bài

Viết hàm editDistance(s, t, ci, cd, cr):

• Input: hai chuỗi s, t (mỗi chuỗi tối đa 1000 ký tự) và ba số nguyên không âm: ci là giá chèn một ký tự vào s, cd là giá xoá một ký tự của s, cr là giá thay một ký tự của s bằng ký tự khác.
• Output: tổng giá nhỏ nhất của một dãy phép sửa biến s thành t.
• Ký tự khớp nhau thì không tốn gì. Chiều biến đổi là s thành t: ci luôn tính cho ký tự có trong t mà thiếu ở s.

Test cases

Hai dòng chuỗi rỗng là ca biên cũng là base case của bảng. Cách liệt kê ca như vậy nằm ở bài edge case.

Hai dòng 2 và 3 chỉ khác nhau hướng biến đổi, nhưng đáp án lệch nhau 9. Nếu cả hai ra cùng một số, bạn đã lẫn chèn với xoá.