Given a string input_string and a list of unique strings dictionary_words, return all possible sentences formed by inserting spaces into input_string such that every segment is a word in dictionary_words. Each word in dictionary_words can be used multiple times. Return the list of sentences in any order. If no segmentation is possible, return an empty list.
Example 1
Input: input_string=fastcar, dictionary_words=[fast,car,fa,st,c,ar]
Output: [fast car,fa st car,fast c ar,fa st c ar]
Explanation: All possible segmentations using dictionary_words.
Example 2
Input: input_string=bluegreen, dictionary_words=[blue,green,blu,eg,reen]
Output: [blue green,blu eg reen]
Explanation: Possible sentences are blue green and blu eg reen.
Example 3
Input: input_string=quickbrownfox, dictionary_words=[quick,brown,fox,qui,ck,bro,wn,fo,x]
Output: [quick brown fox,qui ck brown fox,quick bro wn fox,quick brown fo x,qui ck bro wn fox,quick bro wn fo x,qui ck brown fo x,qui ck bro wn fo x]
Explanation: All valid segmentations.
Constraints
Case 1
Input: input_string='redblue', dictionary_words=['red','blue','re','d','blu','e']
Expected: ['red blue','re d blue','red blu e','re d blu e']
Case 2
Input: input_string='yellow', dictionary_words=['yellow','y','ell','ow','ye','ll','oww']
Expected: ['yellow','y ell ow','ye ll ow']
Case 3
Input: input_string='abcdef', dictionary_words=['ab','abc','cd','def','abcd','ef','c','d','e','f']
Expected: ['ab cd ef','abc d ef','abcd ef','ab c d ef','ab c d e f','abc d e f','abcd e f']
Case 4
Input: input_string='nomatch', dictionary_words=['no','matcha','tea']
Expected: []
Case 5
Input: input_string='aabb', dictionary_words=['a','aa','b','bb','ab']
Expected: ['a a b b','aa b b','a ab b','aa bb','a a bb','a ab b']