Ctrl K

Самая короткая склейка

Средняя
Дан массив непустых слов words. Склейка двух строк x и y — это x, за которым идёт y; но если последняя буква x совпадает с первой буквой y, одна из этих двух букв выбрасывается. Например, склейка ab и ba — это aba, а ab и cde — abcde. Начинаем со строки words[0]. Затем по очереди для каждого следующего слова words[i] выбираем, куда его приклеить: в конец текущей строки (склейка строки и слова) или в начало (склейка слова и строки). Верните наименьшую возможную длину строки после того, как приклеены все слова.
Пример 1
words=['xy', 'zx'] → 3

Если приклеить zx спереди, буквы x на стыке совпадут, и получится zxy длины 3. Приклеив сзади, получили бы xyzx.

Пример 2
words=['ab', 'bc', 'ca'] → 4

ab + bc = abc, затем abc + ca = abca. Короче 4 не получить.

Пример 3
words=['k'] → 1

Склеивать нечего, ответ — длина единственного слова.

Ограничения
  • 1 ≤ len(words) ≤ 1000
  • 1 ≤ len(words[i]) ≤ 50
  • Слова состоят из строчных латинских букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиРазбиение на слова из словаря СредняяФраза на табло СредняяБитовые строки в пределах бюджета СредняяСлова, спрятанные в тексте СредняяСлово растёт по букве Средняя
загружаем Python…
Вход
words=['xy', 'zx']
Ожидается
3

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