140. Word Break II

https://leetcode.com/problems/word-break-ii/

Solution:
May use DSF. In order to reduce the time complexity, we can pre-build a one dimensional array dp[i] to represents that the sub-string from i to n can be segmented into words.

Code:

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        vector<string> res;
        int l = s.size(); 
        if(!l) return res;
        vector<bool> dp(l+1, false);
        dp[l] = true;
        for(int i=l-1; i>=0; --i){
            for(int j=l; j>i; --j){
                if(wordDict.find(s.substr(i, j-i)) != wordDict.end() && dp[j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        wBDSF(s, wordDict, dp, 0, "", res);
        return res;
    }
private:
    void wBDSF(string s, unordered_set<string> &w, vector<bool> &dp, int ind, string t, vector<string> &r){
        if(ind == s.size()) r.push_back(t);
        else{
            for(int i=ind; i<s.size(); ++i){
                string t1 = s.substr(ind, i-ind+1);
                if(w.find(t1) != w.end() && dp[i+1]){
                    wBDSF(s, w, dp, i+1, t.empty()?t+t1:t+" "+t1, r);
                }
            }
        }
    }
};