1239. Word Break II — All Sentence Splits

Given a string s and a dictionary wordDict, add spaces to s to build every sentence where each word is in the dictionary (words may be reused). Return all such sentences in ascending lexicographic order. The input is JSON {s, wordDict}.

Input: JSON {s, wordDict}.

Output: Array — all valid sentences, sorted ascending.

Examples

Input: {"s":"catsanddog","wordDict":["cat","cats","and","sand","dog"]}
Output: ["cat sand dog","cats and dog"]
Explanation: Two valid segmentations.

Input: {"s":"catsandog","wordDict":["cats","dog","sand","and","cat"]}
Output: []
Explanation: No valid segmentation.

Input: {"s":"aa","wordDict":["a"]}
Output: ["a a"]
Explanation: Reuse the dictionary word.

Constraints

• 1<=|s|<=20
• 1<=|wordDict|<=1000

Asked by