leetcode Question: Word Break II

Word Break II

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"].

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

Analysis:

For the "Return all" problems, usually DFS or BFS will work well.
In this problem, a DFS with a simple cutting edge condition will pass all the test cases.
However, I think definitely my solution is not an optimal one. Better idea will be updated later.
For the first two trail, I used different DFS scheme but all failed the last test case. (see the commented part of the code below.)

It seems that the last test case will cause the "time exceed" error:

Last executed input:

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

All the searching rounds in this case are not needed because this string has no solutions (last "b" cannot match any word in dict).

So, according to the idea of the previous question word break I, after get the index array mp, a initial test is provided and if there is no possible solution, no searching is needed and return the empty vector.

Code:

class Solution {
public:

    /*void dfs_0(string &s, int st, vector<int> &sp, vector<string> &res,unordered_set<string> &dict){
        if (st>=s.size()){
            string str=s;
            for (int i=0;i<sp.size();i++){
                str.insert(sp[i]+i," ");
            }
            res.push_back(str);
        }else{
            for (int ed = st; ed<s.size();ed++){
                if (dict.find(s.substr(st,ed-st))!=dict.end()){
                    sp.push_back(ed+1);
                    DFS(s,ed+1,sp,res,dict);
                    sp.pop_back();
                }
            }
        }
    }*/
    
    /*void dfs_1(string &s, int st,vector<int> &sp, vector<string> &res,unordered_set<string> &dict){
        if (st>=s.size()){
            string str=s;
            for (int i=0;i<sp.size();i++){
                str.insert(sp[i]+i," ");
            }
            res.push_back(str);
        }else{
            for (unordered_set<string>::iterator it = dict.begin();it!=dict.end();it++){
                string  ss = *it;
                int sz = ss.size();
                if (s.compare(st,sz,ss)==0){
                    sp.push_back(st+sz);
                    dfs(s,st+sz,sp,res,dict);
                    sp.pop_back();
                }
            }
        }
    }*/

    void dfs(string &s, int st,vector<int> &sp, vector<string> &res,unordered_set<string> &dict, vector<vector<bool> > &mp){
        if (st>=s.size()){
            string str=s;
            for (int i=0;i<sp.size()-1;i++){
                str.insert(sp[i]+i," ");
            }
            res.push_back(str);
        }else{
            for (int j=0;j<mp[st].size();j++){
                if (mp[st][j]==true){
                    sp.push_back(j+1);
                    dfs(s,j+1,sp,res,dict,mp);
                    sp.pop_back();
                }
            }
        }
    }

    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<vector<bool> > mp(s.size(),vector<bool>(s.size(),false));
        for (int i=0;i<s.size();i++){
            for (int j=i;j<s.size();j++){
                if (dict.find(s.substr(i,j-i+1))!=dict.end()){
                    mp[i][j]=true;
                }
            }
        }
        bool flag =false;
        for (int i=0;i<s.size();i++){
            if (mp[i][s.size()-1]){
                flag = true; break;
            }
        }
        vector<string> res;
        vector<int>sp;
        if (!flag){return res;}
        dfs(s,0,sp,res,dict,mp);
        return res;
    }
};