140. Word Break II

problem description

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:
[]

algorithm thought

和上一题计算数量不同，这里需要列出结果。

计算结果需要用到回溯法，但是单纯的回溯在这里太慢了，这里可以加入一种备忘录的方法，类似dp。可以减少我们再回溯中的重复计算，举个例子，如果一个字符串是由很多个一样的子串拼接在一起的，对于回溯法，对于每个子串都是一样的计算，但是加入备忘录之后，对于同样的子串，只需要计算一次就能得到结果。

code

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

    void combin(string&word,vector<string>&prev){
        for(int i=0;i<prev.size();++i){
            prev[i]+=" ";
            prev[i]+=word;   
        }
    }
    vector<string> wordbreak(string&s, unordered_set<string>& worddict) {
        if(m.count(s))
            return m[s];
        vector<string> res;
        if(worddict.count(s)){
            res.push_back(s);
        }
        for(int i=s.size()-1;i>0;--i){
            string tmp=s.substr(i);
            if(worddict.count(tmp)){
                string pr=s.substr(0,i);
                vector<string> prev=wordbreak(pr,worddict);
                combin(tmp,prev);
                res.insert(res.end(),prev.begin(),prev.end());
            }
        }
        return m[s]=res;
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> worddict=unordered_set<string>(wordDict.begin(),wordDict.end());
        return wordbreak(s,worddict);
    }
};

algorithm analysis

这里时间复杂度不太好分析,对于不加入备忘录的算法，时间复杂度是O(2^n)，需要遍历出每一种组合。

加入备忘录之后，能减少很多额外计算了