Войти Регистрация
Алгоритмы

161. Все способы прочитать хештег

Сложная

Хештег tag написан слитно строчными латинскими буквами, words — словарь слов. Разбиение — запись tag словами из словаря через пробел; слово можно использовать сколько угодно раз.

Верните все разбиения, отсортированные как строки. Если разбиений нет — пустой список.

Гарантируется, что разбиений не больше 1000, а их суммарная длина не больше 2·10⁵ символов. Тупиковых веток при этом может быть экспоненциально много.

В работе: Поиск по хештегам во VK Клипах: `#kotiki2026` и `#kotikitut` надо разбить на слова, чтобы найти клипы по каждому слову.

Пример 1

Ввод
tag = "vkvideolive"
words = ["vk", "video", "live", "vkvideo", "deo", "vi"]
Вывод
["vk vi deo live", "vk video live", "vkvideo live"]

`vk video live`, `vk vi deo live`, `vkvideo live`.

Пример 2

Ввод
tag = "aaab"
words = ["a", "aa"]
Вывод
[]

Буква `b` не слово — разбиений нет, хотя начало разбивается многими способами.

Ограничения

  • 0 ≤ длина tag ≤ 10⁵
  • 1 ≤ длина words ≤ 1000, длина слова от 1 до 20
  • Разбиений не больше 1000
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def hashtag_splits(tag, words):
Динамическое программированиеПеребор с возвратомСтрокицельO(n)

Источник: наша задача на данных VK. Условие пересказано своими словами.