Bottom-to-top & Top-to-bottom C++ Solutions, but cost 21ms&28ms. How to optimize them?


  • 0
    Y

    ###I got AC but they are a bit slow.
    ###I think I did used DP in the second solution. So, what should I do to optimize my code?
    ##Thanks a lot!

    #1.Bottom-to-top

      class Solution {
    public:
        vector<string> wordBreak(string s, unordered_set<string> &dict) {
    		line = &s;
        	len = s.length();
    		mark_prvshead = new vector<int> [len+1];
    		bool can = false;
    		deque<int> point_cut(1,0);
    		for(int tail=1;tail<len+1;tail++){
    			bool found = false;
    			for(auto iter = point_cut.begin();iter!=point_cut.end();iter++){
    				int head = *iter;
    				string word = s.substr(head,tail-head);
    				auto ptr_find = dict.find(word);
    				if(ptr_find!=dict.end()){
    					mark_prvshead[tail].push_back(head);
    					found = true;
    				}
    			}
    			if(found)
    				point_cut.push_front(tail);
    
    		}
    		if(point_cut[0]==len)
    			bottom_to_top(len,"");
    		return sentence;
        }
    	void bottom_to_top(int tail,string suffix){
    		auto vec = mark_prvshead[tail];
    		for(auto ptr = vec.begin();ptr!=vec.end();ptr++){
    			string word= line->substr(*ptr,tail-*ptr);
    			if(*ptr==0)
    				sentence.push_back(word + suffix);
    			else
    				bottom_to_top(*ptr," "+ word + suffix);
    		}
    	}
    
    private:
    	int len;
    	vector<int> *mark_prvshead;
    	string *line;
    	unordered_set<string> *diction;
    	vector<string> sentence;
    };
    

    #2.Top-to-bottom use DFS
    class Solution {
    public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
    bool can = false;
    line = &s;
    len = s.length();
    mark = new vector<int> [len];
    for(int tail = 1;tail<len+1;tail++){
    for(int head = 0;head<tail;head++){
    string word = s.substr(head,tail-head);
    auto ptr_find = dict.find(word);
    if(ptr_find!=dict.end()){
    if(tail==len)
    can = true;
    mark[head].push_back(tail);
    }
    }
    }
    if(can)
    DFS(0,"");
    return sentence;
    }
    void DFS(int start,string preffix){
    auto vec = mark[start];
    if(vec.empty())
    return;
    for(auto ptr_nexthead=vec.begin();ptr_nexthead!=vec.end();ptr_nexthead++){
    string suffix = line->substr(start,*ptr_nexthead-start);
    if(len == *ptr_nexthead){
    sentence.push_back(preffix+suffix);
    return;
    }
    DFS(*ptr_nexthead,preffix+suffix+" ");
    }
    }
    private:
    int len;
    vector<int> *mark;
    string *line;
    unordered_set<string> *diction;
    vector<string> sentence;
    };


Log in to reply
 

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