Наименьшее число правок

Средняя

Даны две строки source и target. За одну правку можно сделать одно из трёх действий над строкой source: - вставить любую букву в любое место; - удалить любую букву; - заменить любую букву на другую. Верните наименьшее число правок, за которое source превращается в target.

Пример 1

source="table", target="cable" → 1

Достаточно заменить t на c.

Пример 2

source="sunday", target="saturday" → 3

Вставляем a и t после s, затем заменяем n на r: всего 3 правки.

Пример 3

source="", target="go" → 2

Из пустой строки получаем go двумя вставками.

Ограничения

0 ≤ len(source), len(target) ≤ 500
Строки состоят из строчных латинских букв

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

String Dynamic Programming

Вход

source="table", target="cable"

Ожидается

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 135 тестов на сервере, включая скрытые.