Khoảng cách chỉnh sửa xâu

Buổi 04 — Mảng 2D & Chuỗi Dynamic Programming
Points
27
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
matrix
Submissions
Đề bài

Cho hai xâu $A$ và $B$ chỉ gồm các chữ cái tiếng Anh thường. Bạn có thể thực hiện 3 loại phép biến đổi trên xâu $A$:

  1. Chèn một ký tự vào bất kỳ vị trí nào.
  2. Xóa một ký tự bất kỳ.
  3. Thay thế một ký tự bằng một ký tự khác.

Hãy tìm số phép biến đổi ít nhất (Edit Distance / Levenshtein) để biến xâu $A$ thành xâu $B$.

Dữ liệu vào
  • Dòng đầu tiên chứa xâu $A$.
  • Dòng thứ hai chứa xâu $B$.
Dữ liệu ra

Một số nguyên duy nhất là khoảng cách chỉnh sửa nhỏ nhất giữa $A$ và $B$.

Ví dụ
Input Output
kitten
sitting
3
intention
execution
5
Giới hạn

$1 \le |A|, |B| \le 2000$.

Draft saved