You are given a string s with no spaces, and a list of allowed words wordDict.
Put spaces inside s so that it becomes a sentence where every word is in wordDict. Find all the sentences you can make. Return all such sentences in any order.
You may use the same word from wordDict as many times as you want. If no sentence is possible, return an empty list.
Examples
Example 1:
Input: s = "pineapplejuice", wordDict = ["pine","apple","pineapple","juice"]
Output: ["pine apple juice","pineapple juice"]
Explanation: The text can be cut as "pine apple juice" or as "pineapple juice".
Example 2:
Input: s = "catdog", wordDict = ["cat","dog","catdog"]
Output: ["cat dog","catdog"]
Explanation: Both "cat dog" and the single word "catdog" work.
Example 3:
Input: s = "mangle", wordDict = ["man","go"]
Output: []
Explanation: "man" fits at the start, but "gle" cannot be made from the listed words.