Loading problem…
Given a string `s` and a dictionary of strings `wordDict`, add spaces in `s` to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in **any order**. Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1
Input: s = catsanddog, wordDict = ["cat","cats","and","sand","dog"]
Output: ["cat sand dog","cats and dog"]
Explanation: "catsanddog" can be split as "cat sand dog" or "cats and dog". Every piece in both is a dictionary word, and no other split works.
Example 2
Input: s = pineapplepenapple, wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pine applepen apple","pineapple pen apple"]
Explanation: Using "pine" or "pineapple" at the start, and "applepen" or "apple" + "pen" in the middle, gives three valid sentences. Each one covers the whole string with dictionary words.
Example 3
Input: s = catsandog, wordDict = ["cats","dog","sand","and","cat"]
Output: []
Explanation: No segmentation covers the whole string.
For each starting index, try every dictionary word that matches the prefix from there, then recursively segment the rest. Cache the list of segmentations for each index so overlapping suffixes aren't recomputed.
Run checks all cases above. Submit evaluates all test cases.