Ctrl K

Буквы кратчайших покрытий

Сложная
Дан список различных двухбуквенных строк pairs. Строку назовём **покрытием**, если каждая строка из pairs входит в неё как подпоследовательность (буквы идут в нужном порядке, но не обязательно подряд). **Кратчайшие покрытия** — покрытия наименьшей возможной длины. Опишите каждое кратчайшее покрытие его составом: массивом из 26 чисел, где i-е число — сколько раз в строке встречается i-я буква латинского алфавита. Покрытия, которые отличаются лишь порядком букв, дают одинаковый состав. Верните все различные составы кратчайших покрытий в любом порядке.
Пример 1
pairs=["xy", "yx"] → [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0]]

Кратчайшие покрытия — "xyx" и "yxy". В первом две x и одна y, во втором наоборот, это разные наборы букв.

Пример 2
pairs=["ab", "bc"] → [[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

Единственное кратчайшее покрытие — "abc", каждая буква по разу.

Пример 3
pairs=["qq"] → [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

Чтобы "qq" было подпоследовательностью, нужны две буквы q.

Ограничения
  • 1 ≤ len(pairs) ≤ 256
  • Каждая строка pairs состоит из двух строчных латинских букв
  • Все строки pairs различны
  • Всего в pairs не больше 16 различных букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПорядок букв по словарю СложнаяПуть в дереве без одинаковых соседей СложнаяИмена с обменом первых букв СложнаяЧто можно приготовить СредняяРаскрыть шаблон с переменными Средняя
загружаем Python…
Вход
pairs=["xy", "yx"]
Ожидается
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0]]

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