Khoảng cách chỉnh sửa

Bối cảnh và bài toán

Bạn cần biến chuỗi nguồn thành chuỗi đích bằng ba thao tác, mỗi thao tác giá 1: chèn một ký tự, xóa một ký tự, hoặc thay một ký tự.

Yêu cầu

Tìm số thao tác ít nhất.

Input

Hai dòng chứa hai chuỗi.

Output

In khoảng cách chỉnh sửa nhỏ nhất.

Ràng buộc

• 1 <= |s|,|t| <= 3000
• Chuỗi gồm chữ cái Latin không có khoảng trắng.

Chấm điểm

Ví dụ 1

Input

LOVE
MOVIE

Output

2

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

kitten
sitting

Output

3

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Edit Distance. Bản FULLHOUSE DEV đã biên tập bối cảnh/format và ràng buộc khi cần để khớp scope-lock của khóa học.