My readable c++ DP solution 44ms


  • 0
    P

    DP solution based on the previous problem. Using a struct containing pointers to help trace back.

    class Solution {
    public:
    	struct pNode    //help us trace back the possible solution
    	{
    		int index;   		   
    		vector<pNode*> previous;   //the pointers point to previous word, which could make a valid word-break; 
    		bool valid;     //from the beginning to the current character, if it can be validly word-broken; actually it is useless since this variable can be given by if previous is empty
    		pNode(int x):index(x),valid(0){previous.clear();}
    	};
    	void dfs(pNode* curNode,vector<string> &res,string s)   //Recursion tracing back
    	{
    		if (curNode->index == -1)
    		{
    			res.push_back(s);
    			return;
    		}
    		s.insert(s.begin()+curNode->index+1,' ');
    		for (int i=0;i<curNode->previous.size();i++)
    		{
    			dfs(curNode->previous[i],res,s);
    		}
    		s.erase(curNode->index+1,1);
    	}
    	vector<string> wordBreak(string s, unordered_set<string> &dict) {
    		vector<string> res;
    		int n = s.size();
    		if(n == 0)
    			return res;
    
    		pNode** trace = new pNode*[n];
    		for (int i=0;i<n;i++)
    		{
    			trace[i] = new pNode(i);
    		}
    		pNode* head = new pNode(-1);  //a flag
    		for (int i=0;i<n;i++)    //DP solution
    		{
    			auto tmp = dict.find(s.substr(0,i+1));
    			if (tmp != dict.end())
    			{
    				trace[i]->previous.push_back(head);
    				trace[i]->valid = true;
    			}
    			for (int j=1;j<=i;j++)
    			{
    				if (trace[j-1]->valid)
    				{
    					auto tmp = dict.find(s.substr(j,i-j+1));
    					if (tmp != dict.end())
    					{
    						trace[i]->previous.push_back(trace[j-1]);
    						trace[i]->valid = true;
    					}
    				}
    			}
    		}
    		for (int i=0;i<trace[n-1]->previous.size();i++)  //tracing back
    		{
    			dfs((trace[n-1]->previous)[i],res,s);
    		}
    		delete head;
    		delete[] trace;
    		return res;
    	}
    };

Log in to reply
 

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