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 l-1 to zero j from i to l-1
  • If s.substr(i,j-i+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 == l-1 || dp[ui+1][l-1] ) and s.substr(x,i-x+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,i-x+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 = l-1; i >= 0; i-- ) {
14             for ( int j = i; j < l; j++ ) {
15                 string sub = s.substr(i,j-i+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][l-1] ) {
37             return;
38         }
39         for ( int i = x; i < l; i++ ) {
40             if ( dp[x][i]&&( dp[i+1][l-1] || i==l-1 ) ) {
41                 string t = str;
42                 string sub = s.substr(x,i-x+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 };

Loading Disqus comments...
Table of Contents