leetcode[140]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"].

class Solution {
public:
void dfs(string s, map<int,vector<int>> &fmap,int end, string str, vector<string> &res)
{
    if(end<0)
    {
        res.push_back(str.substr(0,str.size()-1));
        return;
    }
    for (int j=0;j<fmap[end].size();j++)
    {
        string str1=s.substr(fmap[end][j]+1,end-fmap[end][j])+" ";
        str=str1+str;
        dfs(s,fmap,fmap[end][j],str,res);
        str=str.substr(str1.size(),str.size()-str1.size());
    }
    return;
}
vector<string> wordBreak(string s, unordered_set<string> &dict) 
{
    vector<string> res;
    if(s.empty()||dict.empty())return res;
    vector<bool> dp(s.length()+1,false);
    dp[0]=true;
    map<int,vector<int>> fmap;
    for(int i=1;i<=s.length();i++)
    {
        for (int j=0;j<i;j++)
        {
            if(dp[j]&&dict.count(s.substr(j,i-j)))
            {
                dp[i]=true;
                if(j>=0)fmap[i-1].push_back(j-1);
            }
        }
    }
    string str="";
    int end=s.length()-1;
    dfs(s, fmap, end, str,res);
    return res;
}
};