word breakII
word breakII
This is harder...
Is this problem really harder? After solved the word break, we can cut this problem into two pieces. The first one is figure out whether the substring between i and j could be cut into words and the second one is get the result out.
How many ways
Assuming that dp[i][j] means the solutions substringi to j.Because we want to get dp[0][l](l stants for the lentgh of string s), so we need update matrix dp from right to left and bottom to top.

l means the length of string s
i from l1 to zero
j from i to l1
 If s.substr(i,ji+1) is in dictionary,
dp[i][j] = 1
.  Make k from i to j, if
dp[i][k] && dp[k+1][j]
,dp[i][j] = 1
Get the result
This is a DFS problem.
 String str is the value we store the path, if we get to the end of the string s, we push str to the result.
 Make i from the position searched(x) to the end, if
dp[x][i] && (i == l1  dp[ui+1][l1] )
and s.substr(x,ix+1) is in the dictionary, put the substr in str and search i+1.
Mistakes
 When I only use
dp[x][i] > 0 && dict.count(s.substr(x,ix+1)) > 0
, I got TLE...  This DP algoritm looks terrible, and I will find out a better way one day.
Code
1 class Solution {
2 private:
3 int dp[1000][1000];
4 vector < string > result;
5 public:
6 vector<string> wordBreak(string s, unordered_set<string> &dict) {
7 result.clear();
8 int l = s.length();
9 if ( 0 == l ) {
10 return result;
11 }
12 memset(dp,0,sizeof(dp));
13 for ( int i = l1; i >= 0; i ) {
14 for ( int j = i; j < l; j++ ) {
15 string sub = s.substr(i,ji+1);
16 if ( dict.count(sub) > 0 ) {
17 dp[i][j] = 1;
18 }
19 for ( int k = i; k < j; k++ ) {
20 if ( dp[i][k]&&dp[k+1][j] ) {
21 dp[i][j] = 1;
22 }
23 }
24 }
25 }
26 string str = "";
27 DFS(s,dict,str,0);
28 return result;
29 }
30 void DFS( string s, unordered_set< string > dict, string& str, int x ) {
31 int l = s.length();
32 if ( x == l ) {
33 result.push_back(str);
34 return;
35 }
36 if ( 0 == dp[x][l1] ) {
37 return;
38 }
39 for ( int i = x; i < l; i++ ) {
40 if ( dp[x][i]&&( dp[i+1][l1]  i==l1 ) ) {
41 string t = str;
42 string sub = s.substr(x,ix+1);
43 if ( dict.count(sub) > 0 ) {
44 if ( "" == str ) {
45 str += sub;
46 } else {
47 str += " "+sub;
48 }
49 DFS(s,dict,str,i+1);
50 str = t;
51 }
52 }
53 }
54 }
55 };