word break

word break

DFS is okay?

I really like brute-force algorithm such as DFS. So I quickly write a DFS to solve this, but this got TLE...

 1 class Solution {
 2 public:
 3     bool wordBreak(string s, unordered_set<string> &dict) {
 4         return dfs(0,s,dict);
 5     }
 6     bool dfs( int x, string s, unordered_set< string > &dict ) {
 7         if ( x == s.length() ) {
 8             return true;
 9         }
10         int l = s.size();
11         for ( int i = 1; i <= l-x; i++ ) {
12             if ( dict.count(s.substr(x,i)) > 0 ) {
13                 if ( dfs(x+i,s,dict) ) {
14                     return true;
15                 }
16             }
17         }
18         return false;
19     }
20 };

A better way

While searching, there is a lot time wasted in searching the same thing. I use mark[][] to save if the substr from i and length j is in dictionary, and this is also got TLE.T_T

 1 class Solution {
 2 private:
 3     int mark[1000][1000];
 4 public:
 5     bool wordBreak(string s, unordered_set<string> &dict) {
 6         int n = s.length();
 7         memset(mark,-1,sizeof(mark));
 8         return dfs(0,s,dict);
 9     }
10     bool dfs( int x, string s, unordered_set< string >& dict ) {
11         if ( x == s.length() ) {
12             return true;
13         }
14         int l = s.size();
15         for ( int i = 1; i <= l-x; i++ ) {
16             if ( mark[x][i] == -1 ) {
17                 mark[x][i] = (dict.count(s.substr(x,i)) > 0);
18             }
19             if ( mark[x][i] == 1 ) {
20                 if ( dfs(x+i,s,dict) ) {
21                     return true;
22                 }
23             }
24         }
25         return false;
26     }
27 };
Because this does not save the part answer to this question, so the last answer can not be updated by some parts answer.

An other brute way

Cutting this problem in to pieces. Ifs.substr(0,i) ands.substr(i,length-i)are both break into the words, the answer is true, otherwise return false. So,recurisively do this. But, this got TLE apparently.

 1 class Solution {
 2 public:
 3     bool wordBreak(string s, unordered_set<string> &dict) {
 4         if ( 0 == s.length() ) {
 5             return false;
 6         }
 7         if ( 0 < dict.count(s) ) {
 8             return true;
 9         }
10         int l = s.length();
11         for ( int i = 1; i < l; i++ ) {
12             if ( wordBreak(s.substr(0,i),dict) && wordBreak(s.substr(i,l-i),dict)  ) {
13                 return true;        
14             }
15         }
16         return false;
17     }
18 };

Better Way

Recursive solution could always transfrom to dynamic programing way. If a string could be cut into words, and there must be serveral points. The substring before the point could be cut into words, and the substring after that point could be cut into words too. And we can iterate from the left to right, if the left could be cut, update each substring next to it could find in the dictionary or not.

 1 class Solution {
 2 public:
 3     bool wordBreak(string s, unordered_set<string> &dict) {
 4         int l = s.length();
 5         if ( 0 == l ) {
 6             return false;
 7         }
 8         int dp[l+1];
 9         memset(dp,0,sizeof(dp));
10         dp[0] = 1;
11         for ( int i = 1; i <= l; i++ ) {
12             if ( dp[i-1] ) {
13                 for ( int j = i; j <= l; j++ ) {
14                     if ( dict.count(s.substr(i-1,j-i+1)) > 0 ) {
15                         dp[j] = 1;
16                     }
17                     if ( dp[l] == 1 ) {
18                         return true;
19                     }
20                 }
21             }
22         }
23         return dp[l];
24     }
25 };

Loading Disqus comments...
Table of Contents