Chỉnh Sửa Tên Khách Tàu Thống Nhất

Mô tả

Nhà ga Hà Nội những ngày cận Tết luôn tấp nập. Chị nhân viên phòng vé vừa in xong một mẻ vé tàu Thống Nhất thì phát hiện hệ thống nhập liệu đã làm sai chính tả tên khá nhiều hành khách. Để không gây khó khăn khi đối chiếu giấy tờ tùy thân ở cửa soát vé, chị cần biết mỗi tên bị sai lệch bao nhiêu bước so với tên chuẩn. Một bước chỉnh sửa là một trong ba thao tác sau:

• Thêm một ký tự vào bất kỳ vị trí nào của chuỗi.
• Xóa một ký tự bất kỳ khỏi chuỗi.
• Thay thế một ký tự tại một vị trí bằng một ký tự khác. Cho hai chuỗi $A$ (tên sai trên vé) và $B$ (tên chuẩn), hãy tính số bước chỉnh sửa ít nhất để biến chuỗi $A$ thành chuỗi $B$.

Đầu vào

• Chuỗi $A$: ký tự chữ cái tiếng Anh in thường, độ dài từ $0$ đến $1000$.
• Chuỗi $B$: ký tự chữ cái tiếng Anh in thường, độ dài từ $0$ đến $1000$.

Đầu ra

• Một số nguyên duy nhất là số bước chỉnh sửa tối thiểu.

Ràng buộc

• $0 \le |A|, |B| \le 1000$.
• Tổng độ dài hai chuỗi không vượt quá $2000$.

Ví dụ

Ví dụ 1:

• Đầu vào: "mit", "minh"
• Đầu ra: 2
• Giải thích: Từ "mit", ta thay 't' thành 'n' và thêm 'h' ở cuối để ra "minh". Cần 2 bước.

Ví dụ 2:

• Đầu vào: "ha", ""
• Đầu ra: 2
• Giải thích: Cần xóa 2 ký tự để biến chuỗi "ha" thành chuỗi rỗng.

Ví dụ 3:

• Đầu vào: "lan", "nam"
• Đầu ra: 2
• Giải thích: Đổi 'l' thành 'n', 'n' thành 'm', giữ nguyên 'a'. Cần 2 bước.