Войти Регистрация
Алгоритмы

159. Сколько правок до имени получателя

Средняя

При переводе по номеру телефона клиент вводит имя получателя typed, банк знает имя владельца счёта actual.

Одна правка — вставка символа, удаление символа или замена одного символа другим. Верните наименьшее число правок, которое превращает typed в actual. Регистр важен: А и а — разные символы.

В работе: Подсказка «Возможно, вы имели в виду Алексей П.» в Альфа-Онлайн: если правок 1–2, это опечатка, если больше — другой человек.

Пример 1

Ввод
typed = "Алексй"
actual = "Алексей"
Вывод
1

Вставить «е» — одна правка.

Пример 2

Ввод
typed = "Мария"
actual = "Марина"
Вывод
2

Заменить «я» на «н» и дописать «а» — две правки.

Ограничения

  • 0 ≤ длина каждой строки ≤ 1000
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def name_edits(typed, actual):
Динамическое программированиеСтрокиРасстояние редактированияцельn2

Источник: наша задача на данных Альфа-Банка. Условие пересказано своими словами.