Khoảng cách chỉnh sửa xâu
Points
27
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
matrix
Đề 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$:
- Chèn một ký tự vào bất kỳ vị trí nào.
- Xóa một ký tự bất kỳ.
- 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$.
Community Discussion