WordBreakII.cc in leetcode.com

WordBreakII.cc

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<bool> dp(s.length() + 1);
        map<int, vector<int> > trace;
        dp[0] = true;
        for (int b = 0; b < s.length(); ++b) {
            for (int e = b + 1; dp[b] && e <= s.length(); ++e) {
                if (dict.count(s.substr(b, e - b))) {
                    dp[e] = true;
                    trace[e].push_back(b);
                }
            }
        }
        vector<string> ans;
        vector<pair<int, int> > curr;
        build_path(s, s.length(), dp, trace, curr, ans);
        return ans;
    }
private:
    void build_path(const string &s, int index, vector<bool> &dp, map<int, vector<int> > &trace, 
                    vector<pair<int, int> > &curr, vector<string> &ans) {
        if (!dp[index]) {
            return;
        }
        if (index == 0 && !curr.empty()) {
            string tmp = s.substr(curr.back().first, curr.back().second);
            for (int i = curr.size() - 2; i >= 0; --i) {
                tmp += " " + s.substr(curr[i].first, curr[i].second);
            }
            ans.push_back(tmp);
            return;
        }
        for (auto v : trace[index]) {
            curr.push_back(pair<int, int>(v, index - v));
            build_path(s, v, dp, trace, curr, ans);
            curr.pop_back();
        }
    }
};