Word Break II

Given a string s and a dictionary of words dict, add spaces in s to
construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
Example
Given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].

Login to see Answer and Coaching Session More interview questions