Khoảng cách chỉnh sửa
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho hai xâu ký tự $S$ và $T$. Bạn có thể thực hiện 3 loại phép biến đổi trên xâu $S$:
- Chèn một ký tự vào vị trí bất kỳ.
- Xóa một ký tự.
- Thay thế một ký tự bằng ký tự khác.
Hãy tìm số phép biến đổi ít nhất để biến xâu $S$ thành xâu $T$.
Dữ liệu vào
- Dòng đầu chứa xâu $S$ ($1 \le |S| \le 2000$).
- Dòng thứ hai chứa xâu $T$ ($1 \le |T| \le 2000$).
Dữ liệu ra
Một số nguyên duy nhất là số phép biến đổi ít nhất.
Ví dụ
| Input | Output |
|---|---|
horse<br>ros |
3 |
Giới hạn
- $1 \le |S|, |T| \le 2000$
Community Discussion