101
0/320
Loading content...
You are given a continuous text string without any spaces and a vocabulary list containing valid words. Your task is to insert spaces into the text to form grammatically valid sentences where every word exists in the given vocabulary.
A valid sentence is one where the concatenation of all its words (without spaces) exactly equals the original text, and every word in the sentence appears in the vocabulary.
Return all possible valid sentences that can be formed from the text. The sentences may be returned in any order.
Important Notes:
text = "catsanddog"
vocabulary = ["cat","cats","and","sand","dog"]["cat sand dog","cats and dog"]The text "catsanddog" can be segmented in two ways: • "cat" + "sand" + "dog" → "cat sand dog" • "cats" + "and" + "dog" → "cats and dog" Both segmentations use only words from the vocabulary.
text = "pineapplepenapple"
vocabulary = ["apple","pen","applepen","pine","pineapple"]["pine apple pen apple","pine applepen apple","pineapple pen apple"]The text can be segmented in three valid ways. Notice that "apple" is reused twice in the first segmentation, demonstrating that vocabulary words can be used multiple times.
text = "catsandog"
vocabulary = ["cats","dog","sand","and","cat"][]There is no way to segment "catsandog" into a valid sentence using only the given vocabulary words. The substring "og" cannot be formed by any combination of available words.
Constraints