Word Break 系列

// author: Tecker Yu
// time: 8ms
bool wordBreak(string s, vector<string>& wordDict) {
    int len = s.size();
    vector<int> dp(len+1, 0);
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    dp[0]=1;
    for(int i=1;i<=len;++i) {
        for(int j=i;j<=len;++j) {
            if (dp[i-1] && dict.find(s.substr(i-1, j-i+1))!=dict.end()) dp[j]=1;
        }
    }
    return dp[len];
}

bool wordBreak(string s, unordered_set<string> &dict) {
    if(dict.size()==0) return false;
        
    vector<bool> dp(s.size()+1,false);
    dp[0]=true;
        
    for(int i=1;i<=s.size();i++)
    {
		// 从后往前只要能被组合，就继续查看下一个 i
        for(int j=i-1;j>=0;j--)
        {
            if(dp[j])
            {
                string word = s.substr(j,i-j);
                if(dict.find(word)!= dict.end())
                {
                    dp[i]=true;
                    break;
                }
            }
        }
    }
        
    return dp[s.size()];
}

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        return break_word(s, dict);
    }
    
    vector<string> append(vector<string> & left, string& right) {
        vector<string> res;
        for(auto prefix : left) {
            res.push_back(prefix + " " + right);
        }
        return res;
    }
    
    vector<string>& break_word(string s, unordered_set<string> &dict) {
        if (mem.count(s)) return mem[s];
        
        vector<string> res;
        // 边界：s 在词典中
        if (dict.count(s)) res.push_back(s);
        
        // 遍历分割点
        for(int i=1;i<s.size();++i) {
            string right=s.substr(i);
            if (!dict.count(right)) continue;
            string left=s.substr(0, i);
            // 递归求解左半边和右半边，再加上右边的词
            vector<string> left_res = append(break_word(left, dict), right);
            // 添加进当前的解中
            res.insert(res.end(), left_res.begin(), left_res.end());
        }
        // 记忆化求得的解
        mem[s]=res;
        return mem[s];
    }
private:
    unordered_map<string, vector<string> > mem;
};