140. Word Break II (Hard)

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

Solution 1: DFS+DP 3ms

这道题是之前那道Word Break 拆分词句的拓展，那道题只让我们判断给定的字符串能否被拆分成字典中的词，而这道题加大了难度，让我们求出所有可以拆分成的情况，就像题目中给的例子所示。可以用DFS的套路来解题，但是不是一般的brute force，我们必须进行剪枝优化，因为按照惯例OJ的最后一个test case都是巨长无比的，很容易就Time Limit Exceeded。那么如何进行剪枝优化呢，可以参见网友水中的鱼的博客，定义一个一维数组possible，其中possible[i] = true表示在[i, n]区间上有解，n为s的长度，如果某个区间之前被判定了无解，下次循环时就会跳过这个区间，从而大大减少了运行时间，参见代码如下：

可以加上最大单词的长度来剪枝。

class Solution {
    void dfs(string& s, unordered_set<string>& m, vector<bool>& possible, 
            int maxlen, string out, int pos, vector<string>& res) {
        if (pos == s.size()) {
            out.pop_back();
            res.push_back(out);
            return;
        }
        for (int i = pos+1; i <= min(maxlen+pos,(int)s.size()); ++i) {
            string tmp = s.substr(pos, i-pos);
            if (possible[i] && m.count(tmp)) {
                int oldsize = res.size();
                dfs(s, m, possible, maxlen, out+tmp+' ', i, res);
                if (oldsize == res.size()) possible[i] = false;
            }
        }

    }
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> m;
        vector<bool> possible(s.size(), true);
        int maxlen = 0;
        for (string& word: wordDict) {
            m.insert(word);
            maxlen = max(maxlen, (int)word.size());
        }
        vector<string> res;
        dfs(s, m, possible, maxlen, "", 0, res);
        return res; 
    }
};

Solution 2: DFS+DP 13ms

class Solution {
    unordered_map<string, vector<string>> m;

    vector<string> combine(string word, vector<string> prev) {
        for (int i = 0; i < prev.size(); ++i) {
            prev[i] += " "+word;
        }
        return prev;
    }
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        if (m.count(s)) return m[s]; // take from memory
        vector<string> res;
        if (wordDict.count(s)) {
            res.push_back(s); // a whole string is a word
        }
        for (int i = 1; i < s.size(); ++i) {
            string word = s.substr(i);
            if (wordDict.count(word)) {
                string rem = s.substr(0, i);
                vector<string> prev = combine(word, wordBreak(rem, wordDict));
                res.insert(res.end(), prev.begin(), prev.end());
            }
        }
        m[s] = res; // memorize

        return res;
    }
};