Khoảng cách chỉnh sửa giữa hai xâu ngắn
Khoảng cách chỉnh sửa (còn gọi là khoảng cách Levenshtein) là số phép biến đổi ít nhất để biến
Tiến độ của tôi ở bài này
Điểm và code bạn nộp đượ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: cpp-basics, strings.
Nội dung đề bài
Mô tả bài toán
Khoảng cách chỉnh sửa (còn gọi là khoảng cách Levenshtein) là số phép biến đổi ít nhất để biến xâu này thành xâu kia. Ba phép được phép là chèn một ký tự, xoá một ký tự và thay một ký tự bằng ký tự khác. Bảng hai chiều của bài này là hình mẫu cho mọi bài so khớp xâu về sau.
Yêu cầu
Cho hai xâu chỉ gồm chữ cái thường, hãy tính số phép chèn, xoá, thay ít nhất để biến xâu thứ nhất thành xâu thứ hai.
Quy ước nộp bài
Nộp tệp solution.cpp đọc hai xâu từ stdin (mỗi xâu một dòng) và ghi kết quả ra stdout. Chỉ in một số nguyên trên một dòng, không kèm chữ hay dấu cách thừa.
Input
- Dòng thứ nhất: xâu thứ nhất a, độ dài từ 1 tới 15.
- Dòng thứ hai: xâu thứ hai b, độ dài từ 1 tới 15.
Output
- Một số nguyên trên một dòng là số phép biến đổi ít nhất. Hai xâu giống nhau cho kết quả 0.
Ràng buộc
- Chỉ dùng ba phép chèn, xoá, thay; mỗi phép tính là một bước.
- Xâu không chứa dấu cách nên đọc bằng cin là đủ.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
kitten
sitting
Output
3
Ví dụ 2
Input
abc
abc
Output
0
Giải thích
Cần 3 phép: thay k thành s, thay e thành i, chèn g ở cuối. In ra:
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.
