# Share a 8ms DFS solution with comments / Can anybody help analyzing the time and space comlexity?

• ``````    int min_len=INT_MAX, max_len=0; // min_len means the minimum length of word in wordDict
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
for(auto w:wordDict){
w.size()>max_len ? max_len=w.size() : max_len;
w.size()<min_len ? min_len=w.size() : min_len;
}
unordered_map<int, vector<string>> inter_res;     // inter_res[i] stores all the possible sentence from s[i] to s[size]
if(!wordDict.empty())
wordBreak(s, wordDict, inter_res, 0);
return inter_res[0];
}

void wordBreak(string s, unordered_set<string>& wordDict, unordered_map<int, vector<string>>& inter_res, int start){
if(start==s.size()){  // reach the end of s, return
inter_res[start]={""};
return;
}
for(int end=start+min_len-1;end<min(start+max_len, (int)s.size());end++){   // only need to consider possible length of words in wordDict, which is [min_len, max_len]
string word=s.substr(start, end-start+1);
if(wordDict.find(word)!=wordDict.end()){
if(inter_res.find(end+1)!=inter_res.end())      // if possible sentences of s[end+1 to s.size()] has already existed, then prune the recursion tree here
for(auto e:inter_res[end+1])
if(e=="")
inter_res[start].push_back(word);
else
inter_res[start].push_back(word+ " " + e);
wordBreak(s, wordDict, inter_res, end+1);
for(auto e:inter_res[end+1])
if(e=="")
inter_res[start].push_back(word);
else
inter_res[start].push_back(word+ " " + e);
}
}
}
}
``````

My quesion is what is the time and space complexity without considering stack usage of recursion?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.