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

First, I used a similar algorithm as the one I used in problem Word Break I. However, I met Time Limit Exceeded error. The time complexity is o(n!). I realized I need to use more space to compensate the cost in time.

T(n) = \sum^n-1_(i = 1)(T(i)*T(n – 1))

Instead of storing path in dynamic programming array, I stored the last jump position in it. Finally, backtracking algorithm is used to retrieve the available path.

Reference: http://www.cnblogs.com/easonliu/p/3680966.html

Postorder DFS+DP

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        if(s.size() == 0 || wordDict.empty() == true) return vector<string>();
        vector<int> dp[s.size()]; //store the last step of dp[i]
        for(int i = 0; i < s.size(); i++){
            for(int j = i; j >= 0; j--){
                string str = s.substr(j, i - j + 1);
                if(wordDict.find(str) != wordDict.end()){
                    //str exists in dict
                    if(j == 0 || dp[j - 1].empty() == false){ // this line is important, dynamic programming should use previous elements in array.
                        dp[i].push_back(j);    
                    }
                }
            }
        }
        string path;
        vector<string> paths;
        //retrieve the path
        retrievePath(s, dp, s.size() - 1, path, paths);
        return paths;
    }
    //backtracking 
    void retrievePath(string s, vector<int> dp[], int pos, string path, vector<string>& paths){
        //base condition
        if(pos == -1){
            paths.push_back(path);
        }
        //backtracking
        else if(dp[pos].empty()){
            return ;
        }
        else{
            //ordinary condition
            if(pos != s.size() - 1){
                //not the first step, path is not empty
                path.insert(0, " ");
            }
            for(auto it = dp[pos].begin();  it != dp[pos].end(); it++){
                string newPath = path;
                newPath.insert(0, s.substr(*it, pos - *it + 1));
                retrievePath(s, dp, *it - 1, newPath, paths);
            }
        }
    }
};

Preorder DFS+DP

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        if(s.size() == 0) return vector<string>();
        auto dp = vector<vector<int>>(s.size(), vector<int>());
        for(int i = 0; i < s.size(); i++){
            if(wordDict.count(s.substr(0, i+1)) > 0){
                dp[i].push_back(0);
            }
        }
        for(int i = 0; i < s.size() - 1; i++){
            if(!dp[i].empty()){
                for(int j = i+1; j < s.size(); j++){
                    if(wordDict.count(s.substr(i+1, j - i)) > 0){
                        dp[j].push_back(i+1);
                    }
                }
            }
        }
        return DFS(s, dp, s.size() - 1);
    }
    vector<string> DFS(string& s, vector<vector<int>>& dp, int pos){
        // base condition
        vector<string> ans;
        if(pos < 0){
            ans.push_back("");
            return ans;
        }
        for(auto it = dp[pos].begin(); it!= dp[pos].end(); it++){
            auto thisAns = DFS(s, dp, *it - 1);
            for(auto itthisAns = thisAns.begin(); itthisAns != thisAns.end(); itthisAns++){
                if(!(*itthisAns).empty()) (*itthisAns).push_back(' ');
                (*itthisAns).append(s.substr(*it, pos - *it + 1));
                ans.push_back(*itthisAns);
            }
        }
        return ans;
    }
};