C++ solution using dp and backtrace(8ms)


  • 4
    Z
    1. using dp to just like "work break".

    2. backtrace with dp.

      class Solution {

       vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
           if(s.empty() || wordDict.empty()) return vector<string>();
           int n = s.size();
           vector<bool> dp(n+1, false);
           dp[n] = true;
           
           for(int i=n-1; i >= 0; --i)
               for(int j=i+1; j <= n; ++j)
                   if(dp[j] && wordDict.find(s.substr(i, j-i)) != wordDict.end()) {
                       dp[i] = true;
                       break;
                   }
           if(!dp[0]) return vector<string>();
           
           vector<string> ret;
           bt(s, 0, wordDict, dp, ret);
           return ret;
       }
      
       void bt(string &s, int idx, unordered_set<string> &dict, vector<bool> &dp, vector<string> &ret) {
           static string tmp;
           if(idx == s.size()) {
               ret.push_back(tmp);
               return ;
           }
           for(int i=idx+1; i <= s.size(); ++i) {
               string str(s, idx, i-idx);
               if(dp[i] && dict.find(str) != dict.end()) {
                   if(idx != 0) tmp += " ";
                   tmp += str;
                   cout << tmp << endl;
                   
                   bt(s, i, dict, dp, ret);
                   
                   if(idx == 0) tmp.erase(tmp.size()-str.size());
                   else tmp.erase(tmp.size()-str.size()-1);
               }
           }
       }
      

      };


  • 0
    Y

    Why tmp.erase(tmp.size()-str.size())? Is the motivation of this to restore the value of temp to before recursion state? While this sentence would erase from 0 pos for tmp.size()-str.size() number of chars, which effectively makes tmp equals str. Could you kindly explain?


  • 0
    Z

    That is for erasing a white space and the last word in tmp. And you misremember the funtion erase.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.