My DP Solution less than 50 ms, using graph to record the path


  • 3
    V

    The key idea is very similar to Word Break.
    The difference is that you need to record the path, so here I set up a graph to record the path.

    struct Node
    {
    	bool flag;
    	int index;
    	vector<Node*> p;
    	Node():flag(false),index(0){}
    };
    
    string convert(vector<string> path){
    	string str;
    	//ignore the first element empty string
    	for(int i=1;i<path.size()-1;i++) str=str+path[i]+" ";
    	str+=path.back();
    	//cout<<str<<endl;
    	return str;
    }
    
    void dfs(Node* nd, vector<string> &res, int lastIdx, 
    	vector<string> &path, string s, unordered_set<string> &dict)
    {
    	//the first element is empty string
    	path.push_back(s.substr(lastIdx, nd->index - lastIdx));
    	if(nd->p.size()==0){
    		res.push_back(convert(path));
    	}
    	else{
    		for(int i=0;i < nd->p.size();i++){
    			dfs(nd->p[i],res,nd->index,path,s,dict);
    		}
    	}
    	path.pop_back();
    }
    
    vector<string> wordBreak(string s, unordered_set<string> &dict)
    {
    	vector<Node> dp(s.size()+1);
    	for(int i=0;i<dp.size();i++)dp[i].index=i;
    	dp[s.size()].flag=true;
    	for(int i=s.size()-1;i>=0;i--){
    		for(int j=i;j<s.size();j++){
    			string str=s.substr(i,j-i+1);
    			if(dict.find(str)!=dict.end() && dp[j+1].flag){
    				dp[i].flag=true;
    				Node *pt=&dp[j+1];
    				dp[i].p.push_back(pt);
    			}
    		}
    	}
    	//for(int i=0;i<dp.size();i++){
    	//	if(dp[i].p.size()==0)continue;
    	//	cout<<i<<',';
    	//	for(int j=0;j<dp[i].p.size();j++){
    	//		cout<<dp[i].p[j]->index<<',';
    	//	}
    	//	cout<<endl;
    	//}
    	vector<string> res;
    	if(!dp[0].flag) return res;
    	vector<string> path;
    	dfs(&dp[0], res, 0, path, s, dict);
    	//cout<<"existence: "<<dp[0].flag<<endl;
    	return res;
    }

Log in to reply
 

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