Модуль: 11.1E Динамическое программирование. Часть 5_Двумерная динамика


Задача

12 /14


Идентичные строки


Задача

Вам даны две строки s1 и s2. За один шаг вы можете удалить из любой строки ровно один символ. Определите минимального количество шагов, необходимое для того, чтобы сделать строки s1 и s2 идентичными.


Входные данные
Программа получает на вход две строки s1 и s2.

Ограничения

  • 1 <= длина s1 и s2 <= 500;
  • s1 и s2 состоят из маленьких английских букв.

Выходные данные
Выведите ответ на задачу.
 
 
Примеры
Входные данные Выходные данные Примечание
1
sea
eat
2
Вам нужно сделать один шаг, чтобы превратить "sea" в "ea", и еще один шаг, чтобы превратить "eat" в "ea".

time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python31
С++ Mingw-w641
Комментарий учителя