A text message arrived with all its spaces removed: text. You have a list words of allowed words.
Return every way to put spaces back into text so that each resulting word is in words. Each
answer is a single string with the words separated by one space. Words may be used more than once.
Answers may be returned in any order.
Examples
Input: text = "sunflowerseed",
words = ["sun", "flower", "sunflower", "seed", "flowers", "eed"]
Output: ["sun flower seed", "sunflower seed", "sun flowers eed"]
Input: text = "abc", words = ["ab"]
Output: []
Input: text = "gogo", words = ["go"]
Output: ["go go"]
Constraints
1 <= len(text) <= 20,1 <= len(words) <= 12, lowercase letters- The number of answers is at most a few hundred.
Goals
- Segment a string by trying each dictionary word as the next prefix
- Collect every complete segmentation, not just the first