Ctrl K

Склейка фрагментов

Сложная
Лаборатория прочитала длинную цепочку по кусочкам и получила набор фрагментов fragments. Нужно собрать самую короткую строку, в которой каждый фрагмент встречается как подстрока (непрерывный кусок). Ни один фрагмент не является подстрокой другого, все фрагменты различны. Гарантируется, что самая короткая такая строка единственна. Верните её.
Пример 1
fragments=["gatt", "ttaca", "acag"] → 'gattacag'

"gatt" и "ttaca" перекрываются на "tt" — получается "gattaca"; дальше "acag" перекрывается с ней на "aca": итог "gattacag" из 8 букв.

Пример 2
fragments=["cde", "abc"] → 'abcde'

"abc" + "cde" с общей "c" дают "abcde". В обратном порядке перекрытия нет, получилось бы 6 букв.

Пример 3
fragments=["hello"] → 'hello'
Ограничения
  • 1 ≤ len(fragments) ≤ 12
  • 1 ≤ len(fragments[i]) ≤ 20
  • Фрагменты состоят из строчных латинских букв
  • Все фрагменты различны, и ни один не входит в другой как подстрока
  • Самая короткая строка единственна
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиЛучший набор слов из фишек СложнаяКак рассчитаться за меньше переводов СложнаяДве группы с одинаковым средним СложнаяЦепочки с квадратными суммами СложнаяСамая маленькая команда со всеми навыками Сложная
загружаем Python…
Вход
fragments=["gatt", "ttaca", "acag"]
Ожидается
'gattacag'

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