Ctrl K

Лента со словами-окончаниями

Средняя
Нужно записать набор слов words на одну ленту так, чтобы каждое слово можно было прочитать с какой-то позиции ленты до ближайшего символа #. Лента обязательно заканчивается символом #. Коротким словам не всегда нужна своя запись: если слово совпадает с окончанием другого слова, его можно читать с середины уже записанного. Например, на ленте paint# слово int начинается с позиции 2. Верните минимально возможную длину ленты (вместе со всеми символами #).
Пример 1
words=["stone", "one", "tone", "rope"] → 11

Лента stone#rope# длиной 11: one и tone читаются с середины stone до решётки, а rope нужна отдельная запись.

Пример 2
words=["cat", "at", "bat"] → 8

at — окончание и cat, и bat, но сами cat и bat друг в друга не входят: cat#bat#, длина 8.

Пример 3
words=["go", "go"] → 3

Повторяющиеся слова могут ссылаться на одно место ленты: go#, длина 3.

Ограничения
  • 1 ≤ len(words) ≤ 10⁴
  • 1 ≤ len(words[i]) ≤ 20
  • Слова состоят только из строчных латинских букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиРазбиение на слова из словаря СредняяПодсветить найденное СредняяСократить слова до корней СредняяСамые частые запросы СредняяСлово, выращенное по букве Средняя
загружаем Python…
Вход
words=["stone", "one", "tone", "rope"]
Ожидается
11

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