Word Break II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/word-break-ii/

题目：
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].

代码：

 class Solution {  
 public:  
   //Version 1: DFS  
   vector<string> wordBreak(string s, unordered_set<string> &dict) {  
     vector<string> res;  
     if (!wordBreakPossible(s, dict)) { // timeout if not check this! TLE  
       return res;   
     }  
     wordBreakHelper(s, dict, 0, "", res);  
     return res;  
   }  
     
   void wordBreakHelper(const string &s, unordered_set<string> &dict,   
            int start, string sentence, vector<string> &res) {  
     if (start == s.size()) {  
       res.push_back(sentence);  
       return;  
     }  
     if (start != 0) {  
       sentence.push_back(' '); // gap between words        
     }  
   
     for (int i = start; i < s.size(); ++i) {  
       string word = s.substr(start, i - start + 1);  
       if (dict.find(word) == dict.end()) {  
         continue;  
       }  
       wordBreakHelper(s, dict, i+1, sentence + word, res);  
     }  
   }  
     
   bool wordBreakPossible(const string &s, const unordered_set<string> &dict) {  
     int N = s.size();  
     vector<bool> canBreak(N+1, false);  
     canBreak[0] = true;  
     for (int i = 1; i <= N; ++i) {  
       for (int j = i - 1; j >= 0; --j) {  
         if (canBreak[j] && dict.find(s.substr(j, i - j)) != dict.end()) {  
           canBreak[i] = true;  
           break;  
         }  
       }  
     }  
     return canBreak[N];  
   }  
 };  
   
   
 class Solution {  
 public:  
   //Version 2: dp: map<string, vector<string> >  
   typedef unordered_map<string, vector<string> > MAP;  
   vector<string> wordBreak(string s, unordered_set<string> &dict) {  
     MAP map;  
     return wordBreak(s, dict, map);  
   }  
     
   vector<string> wordBreak(string s, unordered_set<string> &dict, MAP &map) {  
     vector<string> result;  
     if (s.size() == 0) return result;  
     if (map.find(s) != map.end()) { // memory search  
       return map[s];  
     }  
     for (int len = 1; len <= s.size(); ++len) {  
       string prefix = s.substr(0, len);  
       if (dict.find(prefix) != dict.end()) {  
         if (prefix.size() == s.size()) {  
           result.push_back(s);  
         } else {  
           string post = s.substr(len); // (pos, len)   
           vector<string> items = wordBreak(post, dict, map);     
           for (int i = 0; i < items.size(); ++i) {  
             string item = prefix + " " + items[i];  
             result.push_back(item);  
           }  
         }  
       }  
     }  
       
     map[s] = result;  
     return result;  
   }  
 };