140. Word Break II

Given a non-empty strings and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

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"].

UPDATE (2017/1/4): The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Thoughts:

1. DP + Backtracking! but (TLE)

2. DFS

Code : my TLE solution based on 139

class Solution {  

public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
       int n = s.length();
       if(n == 0) return vector<string>(); 
       unordered_map<int, vector<string>> m;
       m[0] = vector<string>(1,"");

        for(int i = 1; i <= n; i++){
           for(int j = 0; j < i; j++){
               string new2check = s.substr(j, i - j);
               if(m.find(j)!= m.end()&& find(wordDict.begin(), wordDict.end(), new2check)!=wordDict.end()){
                   auto tmp = m[j];
                   for(auto & str: tmp){
                       if(str == "") str+= new2check;
                       else str+=" " + new2check;
                   }
                   m[i].insert(m[i].end(),tmp.begin(),tmp.end());

               }
           }
       }

        return m[n];
    }
};

Code: DFS + map table, TC:O(n^2) for worse , O(n) for best , SC:O(n^2) for worse, O(1) for best (k: num of words in the dictionary)

class Solution {
    unordered_map <string, vector<string>> m;
    vector<string> combine(string w, vector<string> prev){
        for(auto & str: prev){
            str += " " + w;
        }
        return prev;
    }
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        if(m.find(s)!=m.end())return m[s];
        vector<string>ans;

        //whole word
        if(find(wordDict.begin(),wordDict.end(),s)!=wordDict.end()) ans.push_back(s); // or (wordDcict.count(s))
        //break up: i starts from 1
        for(int i = 1; i < s.size(); i++){
            string w = s.substr(i);
            if(find(wordDict.begin(),wordDict.end(),w)!=wordDict.end()) { // or (wordDcict.count(w))
                string rest = s.substr(0,i);
                vector<string> prev_ans = combine(w, wordBreak(rest, wordDict));
                ans.insert(ans.end(), prev_ans.begin(), prev_ans.end());
            }
        }
        m[s] = ans;
        return ans;
    }
};

Code (Java) TC: O(k^2) for worse, O(n) for best, SC:O(k^2) for worse, O(1) for best (k: num of words in the dictionary)

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        return DFS(s, wordDict, new HashMap<String, List<String>>());
    }
    List <String> DFS (String s, List<String> wordDict, Map<String, List<String>> map){
        if(map.containsKey(s)) return map.get(s);

        List<String> ans = new LinkedList<String>();
        if(s.length() == 0) {
            ans.add("");
            return ans;
        }

        for(String word: wordDict){
            if(s.startsWith(word)){
                List<String> restList = DFS(s.substring(word.length()), wordDict, map);
                // System.out.println(restList.size());
               for(String rest: restList){
                   ans.add(word + (rest.isEmpty()?"": " ") + rest);
               }
            }
        }

        map.put(s,ans);
        return ans;
    }
}