140. Word Break II.md

140. Word Break II

思路

这题是139. Word Break的升级版，139题只让我们判断给定的字符串s是否可以拆分成字典中的词，而这题让我们求出所有可以拆分成的情况。139题我们用的是动态规划或者带记忆的递归，此题其实也是类似的。我们用一个cache来记录已经求过的结果，即cache[s]就等于s被拆分的所有情况，那么我们就可根据cache[s去掉某个前缀后的子串]的结果求得cache[s]，伪代码如下：

cache[s] = {}
for word in wordDict:
    if word是s的前缀:
        sub_res = s去掉前缀word后的拆分结果(即递归调用)
        for ss in subres:
            cache[s].push(word + " " + ss)

C++

class Solution {
private:
    unordered_map<string, vector<string>>cache;
    vector<string> helper(string s, const vector<string>& wordDict){
        if(s.empty()) return {""}; // 注意不是空数组, 因为如果为空就代表了无法拆分
        if(cache.count(s)) return cache[s];
        
        vector<string>res;
        for(string word: wordDict){
            if(s.substr(0, word.size()) != word) continue;
            vector<string>subres = helper(s.substr(word.size()), wordDict);
            for(string &ss: subres)
                res.push_back(word + (ss.empty() ? "" : " ") + ss);
        }
        // 如果不能被拆分res将为空数组
        cache[s] = res;
        return res;
    }
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        return helper(s, wordDict);
    }
};