Leet Code Daily 2024-05-25 - Word Break II

class Solution {
public:
    unordered_set<string> wordSet;
    vector<string> wordNow;
    vector<string> ans;

    void dfs(string& s, int i) {
        if (i == s.size()) {
            string sentence;
            for (const auto& w : wordNow) {
                if (sentence.size() > 0) {
                    sentence += " ";
                }
                sentence += w;
            }
            ans.push_back(sentence);
            return;
        }
        for (int j = i + 1; j <= s.size(); j++) {
            string new_word = s.substr(i, j - i);
            if (wordSet.contains(new_word)) {
                wordNow.push_back(new_word);
                dfs(s, j);
                wordNow.pop_back();
            }
        }
    }

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        wordSet = unordered_set<string>(wordDict.begin(), wordDict.end());
        dfs(s, 0);
        return ans;
    }
};