Leetcode: Word Break (Dynamic programming) (Analysis & solutions)

PROBLEM:

Given a string s and a dictionary of words dict, determine if s can be segmented into

a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Hide Tags

 Dynamic Programming

Hide Similar Problems

 (M) Palindrome Partitioning (H) Word Break II

Analysis: (Backtracking)

If we can use backtracking, it's not a difficult problem. See the figure below:

in above example, if in 'a' is not in the dict, then try 'ab', ...., until a matching case is found and then check the remaining string with the same way.

This way is simple and easy to understand, but it does lots of  unnecessary works and waste lost of time, as shown in the figure below. Therefore, in the figure, in the first round, we need to do lots of comparisons (the strings in green circles). If it fails in the first round, and we do the second round. If, for example, 'ab' is in the dict, we continue to do the comparisons with the strings in green circles. You can see the comparisons in first round and second round are the same and therefore they are indeed wasting time. That's why the Dynamic Programming should be used to avoid the repeating works.

///////////////////////////////////////////////////////////////////////////////
//codes in backtracking

class Solution {

public:

       bool wordBreak(string s, unordered_set<string>& wordDict) {

              int size = s.size();

              if (size == 0)return true;

              for (int i = 0; i < size; i++){

                     if (wordDict.find(s.substr(0, i + 1))!=wordDict.end() && wordBreak(s.substr(i+1,size-i-1), wordDict) ){

                           return true;

                     }

              }

              return false;

       }

};

Analysis: (Dynamic programming)

To prevent repeating works, the comparison results should be saved somewhere for future use. When in the future comparison, if we find that the comparison have been done before and we don't need to do it again and just use the results directly. 

Here a vector db is used to store the comparison results: db[i]=1 means that the sub-string (from 0 to i) in string s can find matched words in dict. If in the end, db[s.size()-1]==1, we say the whole string s can find matched words in dict. 

/////////////////////////////////////////////////////////////////////////////
//code in Dynamic programming

class Solution {

public:

       bool wordBreak(string s, unordered_set<string>& wordDict) {

              int size = s.size();

              if (size == 0)return true;

              vector<int> db;

              db.resize(size,0);

              for (int i = 0; i < size; i++){

                     if (wordDict.find(s.substr(0, i + 1)) != wordDict.end()){

                           db[i] = 1;

                     }

                     else if (i>0){

                           for (int j = i; j > 0; j--){

                                  if (db[j-1] && wordDict.find(s.substr(j,i-j+1))!=wordDict.end()){

                                         db[i] = 1;

                                         break;

                                  }

                           }

                     }

              }

              if (db[size - 1] == 1)return true;

              else return false;

       }

};