Accepted C++ solution, but should I cache bool or the results of sub strings?


  • 0
    R

    for each sub string searched, I could cache a Boolean value indicating if there is a solution, or I could cache the complete solutions for the sub string. I wonder which one is better?

    class Solution {
    public:
        vector<string> wordBreak(string s, unordered_set<string> &dict) {
    		vector<string> sentences;
    		this->s = s;
    		this->pos = 0;
    		this->dict = dict;
    		this->sentence = "";
    		wordBreakInternal();
    
    		return this->sentences;
    	}
    private:
    	vector<string> sentences;
    	string s;
    	unsigned int pos;
    	string sentence;
    	unordered_set<string> dict;
    	unordered_map<unsigned int, bool> history;
    
    	bool isEqual(const string &w, unsigned int start)
    	{
    		for (int i = 0; i < w.size(); i++)
    		{
    			if (w[i] != s[start + i])
    			{
    				return false;
    			}
    		}
    
    		return true;
    	}
    
    	void wordBreakInternal()
    	{
    		if (history.find(pos) != history.end() && history[pos] == false)
    		{
    			return;
    		}
    
    		unsigned int len = s.size() - pos;
    		if (len < 1)
    		{
    			history[pos] = false;
    			return;
    		}
    
    		int countBefore = sentences.size();
    
    		for (auto i = dict.begin(); i != dict.end(); i++)
    		{
    			const string &w = *i;
    
    			if (w.size() > len)
    			{
    				continue;
    			}
    
    			if (w.size() == len)
    			{
    				if (isEqual(w, pos))
    				{
    					if (sentence.empty())
    					{
    						sentences.push_back(w);
    					}
    					else
    					{
    						sentences.push_back(sentence + " " + w);
    						sentence = "";
    					}
    				}
    
    				continue;
    			}
    
    			if (!isEqual(w, pos))
    			{
    				continue;
    			}
    
    			pos += w.size();
    			string oldSentence = sentence;
    
    			if (sentence.empty())
    			{
    				sentence = w;
    			}
    			else
    			{
    				sentence = sentence + " " + w;
    			}
    
    			wordBreakInternal();
    
    			pos -= w.size();
    			sentence = oldSentence;
    		}
    
    		if (sentences.size() > countBefore)
    		{
    			history[pos] = true;
    		}
    		else
    		{
    			history[pos] = false;
    		}
        }
    };

  • 0
    R

    There is actually a serious bug in the above code, but yet it passed all the tests!

    The bug is in sentence = ""; where the variable should be reset to the original sentence before the last couple operations.


Log in to reply
 

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