Khoảng cách biến đổi xâu
Points
16
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho hai xâu ký tự $S$ và $T$. Trong một phép biến đổi trên xâu $S$, bạn có thể thực hiện một trong ba thao tác:
- 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 một 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$.
Cấu trúc con tối ưu: $dp[i][j]$ là số phép biến đổi ít nhất để biến $i$ ký tự đầu của $S$ thành $j$ ký tự đầu của $T$.
Dữ liệu vào
Dòng đầu tiên chứa xâu $S$. Dòng thứ hai chứa xâu $T$.
Dữ liệu ra
Một số nguyên duy nhất là khoảng cách biến đổi nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| horse ros |
3 |
| intention execution |
5 |
Giới hạn
$1 \le |S|, |T| \le 1000$, các xâu chỉ gồm chữ cái in thường.
Community Discussion