Контест Senior Задачи на Java обновлено
Расстояние Левенштейна
Условие
Найдите минимальное число операций, чтобы превратить первую строку во вторую. Операции: вставить символ, удалить символ, заменить символ.
Ввод: две строки из строчных латинских букв длиной от 1 до 3000.
Вывод: одно число.
Пример
kitten
sitting
3
Как подойти
DP по префиксам с двумя строками.
Подсказки: 2
- Таблица dp по префиксам.
- Хватит двух строк таблицы.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.