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.
1 <= s.length <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10s and wordDict[i] consist of only lowercase English letterswordDict are unique10^5s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]["cats and dog","cat sand dog"]s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]["pine apple pen apple","pineapple pen apple","pine applepen apple"]s = "catsandog", wordDict = ["cats","dog","sand","and","cat"][]