140. Word Break II

Given a non-empty string s 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. Return all such possible sentences.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.

• You may assume the dictionary does not contain duplicate words.

Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

// Dynamic Programming + Backtracking
void backtracking(int pos, vector<vector<string>> &dp, vector<string> &tmp, vector<string> &res) {
    if (pos == dp.size() - 1) {
        ostringstream ss;
        for (int i = 0; i < tmp.size() - 1; ++i) {
            ss << tmp[i] << " ";
        }
        ss << tmp.back();
        res.push_back(ss.str());
        return;
    }
    
    for (const auto& word : dp[pos]) {
        tmp.push_back(word);
        backtracking(pos + word.size(), dp, tmp, res);
        tmp.pop_back();
    }
}
vector<string> wordBreak(string s, vector<string>& wordDict) {
    vector<vector<string> > dp(s.size() + 1);
    dp.back().push_back("");
    for (int pos = s.size() - 1; pos >= 0; --pos) {
        for (int i = 0; i < wordDict.size(); i++) {
            bool match = true;
            for (int j = 0; j < wordDict[i].size(); ++j) {
                if (pos + j >= s.size() || wordDict[i][j] != s[pos + j]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                if (!dp[pos + wordDict[i].size()].empty()) {
                    dp[pos].push_back(wordDict[i]);
                }
            }
        }
    }
    
    vector<string> res;
    vector<string> tmp;
    backtracking(0, dp, tmp, res);
    return res;
}

// DFS with Hashmap
vector<string> helper(const string& s, vector<string>& wordDict, unordered_map<string, vector<string> >& memo) {
    if (memo.count(s)) return memo[s];
    if (s.empty()) return {""};
    vector<string> res;
    for (const string& word : wordDict) {
        if (s.substr(0, word.size()) != word) continue;
        vector<string> next = helper(s.substr(word.size()), wordDict, memo);
        for (const string& str : next) {
            res.emplace_back(word + (str.empty() ? "" : " ") + str);
        }
    }
    return memo[s] = res;
}
vector<string> wordBreak(string s, vector<string>& wordDict) { // time: O(n^2); space: O(n)
    unordered_map<string, vector<string> > memo;
    return helper(s, wordDict, memo);
}

vector<string> backtracking(string s, unordered_set<string>& dict, unordered_map<string, vector<string> >& memo) {
    if (memo.count(s)) return memo[s];
    vector<string> res;
    for (int pos = s.length() - 1; pos >= 0; --pos) { // loop from the back
        string word = s.substr(pos);
        if (dict.count(word)) {
            if (pos == 0)
                res.push_back(word);
            else {
                vector<string> prev = backtracking(s.substr(0, pos), dict, memo);
                for (string& str : prev) {
                    res.push_back(str + " " + word);
                }
            }
        }
    }
    return memo[s] = res;
}
vector<string> wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    unordered_map<string, vector<string> > memo;
    return backtracking(s, dict, memo);
}

139. Word Break