Quy hoạch động
Mô tả
Tại quầy thủ tục hãng Bamboo Airways, nhân viên mặt đất phải đối chiếu tên hành khách ghi trên vé điện tử với tên trong hộ chiếu. Do lỗi nhập liệu, đôi khi tên trên vé bị sai chính tả, dư hoặc thiếu chữ cái so với tên chuẩn trong hộ chiếu. Để hệ thống tự động nhận diện, bạn cần tính số thao tác sửa đổi ít nhất để biến tên trên vé thành tên chuẩn, chỉ được dùng ba thao tác: chèn một ký tự, xóa một ký tự, hoặc thay thế một ký tự bằng ký tự khác.
Đầu vào
Hai chuỗi ký tự ve và chuan, mỗi chuỗi nằm trên một dòng, chỉ chứa các chữ cái thường từ 'a' đến 'z'.
Đầu ra
Một số nguyên không âm duy nhất là số thao tác tối thiểu cần thực hiện.
Ràng buộc
- Độ dài mỗi chuỗi nằm trong khoảng từ 0 đến 2000 ký tự.
- Có thể có chuỗi rỗng.
Ví dụ
Ví dụ 1:
- Đầu vào:
kata,khanh - Đầu ra:
3 - Giải thích: Thay 'a' tại vị trí 2 thành 'h' ta được 'khha'; chèn 'a' và 'n' ở cuối thành 'khanh'. Cách khác: thay 'a' thứ nhất thành 'h', chèn 'n' rồi 'a'. Cả hai đều tốn 3 thao tác, không thể ít hơn.
Ví dụ 2:
- Đầu vào:
an,an - Đầu ra:
0 - Giải thích: Hai chuỗi đã giống nhau, không cần sửa gì.