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


  • 1
    B
        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);
                    else{                                                            // // if not found, go through the recursion tree
                        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?


Log in to reply
 

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