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.

For example, given

s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is
[ "cats and dog", "cat sand dog" ]

Make sure the strings are sorted in your result.

Interview Code Editor
Hints
  • Solution Approach
  • Complete Solution
1652 successful submissions.
Asked In:
  • IBM
  • Google
Click here to jump start your coding interview preparation