Two method: DFS and DP . Easy to understand,only 8 ms c++


  • 1
    Y
    //This is DFS method 
        class Solution {
        public:
            vector<string> result;
            void dfs(string s, unordered_set<string>& wordDict,string temp){
                if(s.size()==0){
                    temp.erase(temp.end()-1);
                    result.push_back(temp);
                    return ;
                }
                for(int i = 0 ; i <s.size() ; ++i){
                    string sub = s.substr(0,i+1);
                    if(wordDict.find(sub)!=wordDict.end()){
                        string new_s = s.substr(i+1);
                        dfs(new_s,wordDict,temp+sub+" ");        
                    }
                }
                
            }
            vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
                // This part is to avoid the case "aaaaaaaaaa.....b "
                for(int i = s.size() -1; i>=0; --i){
                    if(wordDict.find(s.substr(i))!=wordDict.end() ){
                        break;
                    }
                    if(i==0)
                    return result;
                }
                // This part is for dfs
                string temp;
                dfs(s,wordDict,temp);
                return result;    
            }
        };
    
    
    
    
        //This is DP method 
        class Solution {
        public:
            vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
                vector<string> result;
                if(s.size() ==0){
                    return result;
                }
                for(int i = s.size() -1; i>=0; --i){
                    if(wordDict.find(s.substr(i))!=wordDict.end() ){
                        break;
                    }
                    if(i==0)
                    return result;
                }
                vector<vector<vector<int>>> M(s.size());
                for(int i = 0 ; i <s.size() ; ++i){
                    if(wordDict.find(s.substr(0,i+1))!=wordDict.end() ){
                        vector<int> temp;
                        temp.push_back(i);
                        M[i].push_back(temp);
                    }
                    for(int j = 0 ; j <i;++j){
                        if(M[j].size()!=0&& wordDict.find(s.substr(j+1,i-j))!=wordDict.end() )
                            
                            for(int ii =0 ; ii<M[j].size() ; ++ii ){
                                vector<int> temp = M[j][ii];
                                temp.push_back(i);
                                M[i].push_back(temp);
                            }
                    }
                }
                for(int i = 0 ; i <M[s.size()-1].size(); ++i){
                    vector<int> temp;
                    temp = M[s.size()-1][i];
                    string haha;
                    int pre = 0 ; 
                    for(int j = 0 ; j <temp.size(); ++j){
                        haha = haha + s.substr(pre,temp[j]-pre+1) ;
                        haha = haha + " ";
                        pre = temp[j]+1;
                    }
                    haha.erase(haha.end() - 1);
                    result.push_back(haha);
                }
                return result;
            }
        };

  • 0
    T

    I just copy pasted your DP solution. It gives TLE


Log in to reply
 

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