[Leetcode] Word Break II

Problem

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"].

Algorithm

Subproblem structure: 

Let result[i] be the all possible solutions to break the s.substring(0, i). 

                                   result[i] = result[j] + s.substring(j,i), for all s.substring(j,i) in dict. 

For some extreme cases provided by the OJ of Leetcode, the algorithm above will exceed time limit. 

For example, s = "aaaaaaaaab", dict = ["a","aa"]. 

In this case, we can quickly determine whether it is breakable in O(n^2) using DP in Word Break I. If it is breakable then build the result. 

Code