Редакционное расстояние
Редакционное расстояние между двумя строками — это минимальное количество операций, необходимых для преобразования одной строки в другую. Разрешённые операции:
- Добавить один символ в строку.
- Удалить один символ из строки.
- Заменить один символ в строке.
Например, редакционное расстояние между и равно 2, так как сначала можно заменить на , а затем добавить .
Вам даны две строки, и ваша задача — вычислить их редакционное расстояние.
Ввод
Первая строка входных данных содержит первую строку, а вторая строка содержит вторую. Гарантируется, что количество символов в строках не превышает 1000.
Вывод
Программа должна вывести одно целое число — редакционное расстояние между двумя заданными строками.
Примеры
Ввод | Вывод |
love
movie | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB