Word Break - All Sentences

Problem Statement

Given a non-empty string text and a list of non-empty words called dictList, insert spaces into text to form sentences where each word is contained in dictList. Return all such possible sentences.

Note:

• You can reuse the same word from the dictionary multiple times in the segmentation.
• The dictionary is guaranteed to have no repeated words.

Examples

text = "dogsandcat"
dictList = ["dog", "dogs", "and", "cat"]
Output:
[
  "dogs and cat",
  "dog sand cat"
]

text = "applepenapple"
dictList = ["apple", "pen", "applepen"]
Output:
[
  "apple pen apple",
  "applepen apple"
]

text = "catsandbat"
dictList = ["cats", "dog", "sand", "and", "cat", "bat"]
Output:
[
  "cats and bat",
  "cat sand bat"
]

Constraints

• 1 ≤ length of text ≤ 25
• 1 ≤ number of words in dictList ≤ 20
• All dictionary words and text consist of lowercase English letters only.