Every Way to Space the Words

Hard

You are given a string text with no spaces and a vocabulary vocabulary, a list of words. Insert spaces into text so that every resulting piece is a word from the vocabulary. A word may be used any number of times, and some words may not be used at all. Return every sentence that can be formed this way, in any order. Words in a sentence are separated by a single space. If there is no way, return an empty list.

Example 1

text='sunflowerseed', vocabulary=['sun', 'flower', 'sunflower', 'seed', 'flowers', 'eed'] → ['sun flower seed', 'sun flowers eed', 'sunflower seed']

Three splits work: "sun flower seed", "sunflower seed" and "sun flowers eed".

Example 2

text='abab', vocabulary=['ab'] → ['ab ab']

The same word may be used more than once.

Example 3

text='planet', vocabulary=['plan', 'net'] → []

After "plan" the rest is "et", which is not in the vocabulary, so there are no splits.

Constraints

1 ≤ text.length ≤ 100
1 ≤ vocabulary.length ≤ 1000
1 ≤ vocabulary[i].length ≤ 20
text and vocabulary[i] consist of lowercase English letters only
the answer holds at most 10⁵ sentences

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Trie Memoization Array Hash Table String Dynamic Programming Backtracking

Similar problems

Split Into Dictionary Words Medium Words Hidden in a Text Medium Fewest Stray Letters Medium Words Hidden in a Letter Grid Hard Glued Into a Palindrome Hard

Input

text='sunflowerseed', vocabulary=['sun', 'flower', 'sunflower', 'seed', 'flowers', 'eed']

Expected

['sun flower seed', 'sun flowers eed', 'sunflower seed']

Run checks the first 3 tests in your browser. Submit checks all 62 tests on the server, hidden ones included.