Word Break II -- leetcode

Question:

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

All solutions are:

 ["cats","and","dog"]

["cat","sand","dog"].

Answer:

#include <iostream>

#include <vector>

#include <iostream>

#include <unordered_set>

using namespace std;

void word_break(string str, int idx, unordered_set<string> &set, vector<vector<string>> &res, vector<string> &subres){

    

    int len = str.size();

    

    if(idx == len){             //edge case!

        res.push_back(subres);

    }

    

    for(int i = idx; i < len; ++i){

        

        if(set.count(str.substr(idx,i-idx + 1))){

            subres.push_back(str.substr(idx,i-idx + 1));

            word_break(str, i+1, set, res, subres);

            subres.pop_back();          //backtrack!

            

        }

    }

}

void printV(vector<vector<string>> str){

    for(vector<string> ss:str){

        cout<<"[";

        for(string s: ss){

            cout<<s<<",";

        }

        cout<<"]"<<endl;

    }

    cout<<endl;

};

int main(int argc, const char * argv[]) {

    vector<string> subres;

    vector<vector<string>> res;

    string s= "leetcodecab";

    

    unordered_set<string> set;

    set.insert("leet");

    set.insert("code");

    set.insert("leetcode");

    set.insert("ab");

    set.insert("c");

    

    word_break(s,0,set,res, subres);

    printV(res);

}


--------------------------------------------------------------------------------------------------------------------------

//For original code in leetcode:

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> res;
        string subres;
        wordBreakHelp(s,0,dict,subres,res);
        return res;
    }
   
    void wordBreakHelp(string s, int idx, unordered_set<string> &dict, string & subres, vector<string> & res){
        int len = s.size();
   
        if(idx == len){             //edge case!
            res.push_back(subres.substr(0,subres.length()-1));
            return;
        }
   
    for(int i = idx; i < len; ++i){
   
        int sublen = i-idx+1;
        if(dict.count(s.substr(idx,sublen))){
            subres.append(s.substr(idx,sublen));
            subres.append(" ");
           
            wordBreakHelp(s, i+1, dict, subres, res);
           
            subres.pop_back();
            subres.erase(subres.length()-sublen, sublen);          //backtrack!
        }
    }
    return;
    }

};