Ctrl K

Все способы расставить пробелы

Сложная
Дана строка text без пробелов и словарь vocabulary — список слов. Расставьте в text пробелы так, чтобы каждый получившийся кусок был словом из словаря. Одно слово можно использовать сколько угодно раз, а какие-то слова не использовать вовсе. Верните все предложения, которые так можно получить, в любом порядке. Слова в предложении разделяются одним пробелом. Если ни одного способа нет, верните пустой список.
Пример 1
text='sunflowerseed', vocabulary=['sun', 'flower', 'sunflower', 'seed', 'flowers', 'eed'] → ['sun flower seed', 'sun flowers eed', 'sunflower seed']

Подходят три разбиения: «sun flower seed», «sunflower seed» и «sun flowers eed».

Пример 2
text='abab', vocabulary=['ab'] → ['ab ab']

Одно и то же слово можно использовать несколько раз.

Пример 3
text='planet', vocabulary=['plan', 'net'] → []

После «plan» остаётся «et», а такого слова в словаре нет, так что разбиений нет.

Ограничения
  • 1 ≤ text.length ≤ 100
  • 1 ≤ vocabulary.length ≤ 1000
  • 1 ≤ vocabulary[i].length ≤ 20
  • text и vocabulary[i] состоят только из строчных латинских букв
  • число предложений в ответе не превышает 10⁵
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиРазбиение на слова из словаря СредняяСлова, спрятанные в тексте СредняяМеньше всего лишних букв СредняяСлова в буквенной сетке СложнаяСклеить в палиндром Сложная
загружаем Python…
Вход
text='sunflowerseed', vocabulary=['sun', 'flower', 'sunflower', 'seed', 'flowers', 'eed']
Ожидается
['sun flower seed', 'sun flowers eed', 'sunflower seed']

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