Наибольшая общая подпоследовательность
Medium
Найдите длину наибольшей общей подпоследовательности двух строк (LCS): это максимальная длина строки, которую можно получить удалением символов из обеих исходных (относительный порядок оставшихся символов сохраняется; непрерывность не требуется). Не путать с общей подстрокой — та должна быть непрерывной.
Примеры:
Вход:
{"text1": "abcde", "text2": "ace"}
Выход:
3
Объяснение: "ace" целиком входит в "abcde" с сохранением порядка → длина 3.
Вход:
{"text1": "abc", "text2": "abc"}
Выход:
3
Объяснение: Строки совпадают — общая подпоследовательность равна всей строке, длина 3.
Вход:
{"text1": "abc", "text2": "def"}
Выход:
0
Объяснение: Общих символов нет → длина 0.
Ограничения:
1 <= text1.length, text2.length <= 1000
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!