Контест Middle Динамическое программирование спрашивают часто обновлено
Расстояние Левенштейна между двумя словами
Условие
За одну операцию можно вставить символ, удалить символ или заменить один символ на другой. Найдите минимальное число операций, превращающих строку a в строку b.
Ввод: две строки из строчных латинских букв, каждая длиной от 0 до 1000. Пустая строка записана как -.
Вывод: минимальное число операций.
Пример 1
Ввод:
kitten
sitting
Вывод:
3
Пример 2
Ввод:
-
abc
Вывод:
3
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.