[Word Break]: wrong answer reported by leetcode, but verified by VS no problem.


  • 0
    W

    The error case is very simple:
    Input: "a", ["a"]
    Output: false
    Expected: true

    I have verified the input "a", ["a"]. It has passed by Visual Studio. Could any one help to check my code.

    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
    		if(s.empty()) return false;
    		unordered_set <string> unmatch;
    		unordered_set <string> match;
    		return helper(s, dict, unmatch, match);
        }
    private:
    	bool helper(string s, unordered_set<string> &dict,unordered_set<string> &unmatch, unordered_set<string>&match){
    		if(s.empty()) return false;
    		bool flag = false;
    		for(int i=1; i<s.length(); i++)
    		{
    			string prefixstr=s.substr(0,i); 
    			//prefixstr cannot be empty;
    			//check prefixstr
    			if(!unmatch.count(prefixstr))
    			{
    				if(match.count(prefixstr))
    					flag=true;
    				else
    				{
    					flag=helper(prefixstr, dict,unmatch, match);
    					if(flag)
    						match.insert(prefixstr);
    					else
    						unmatch.insert(prefixstr);
    				}			
    			}
    			// check suffixstr
    			if(flag)
    			{
    				string suffixstr=s.substr(i);
    				//suffixstr could be empty
    				if(!prefixstr.empty())
    				{
    					if(!unmatch.count(suffixstr))
    					{
    						if(match.count(suffixstr))
    							flag=true;
    						else
    						{
    							flag=helper(suffixstr, dict,unmatch, match);
    							if(flag)
    								return true;	//match.insert(suffixstr);
    							else
    								unmatch.insert(suffixstr);
    						}
    					}
    					else
    						return true;
    				}
    			}
    		}
    	}
    };

  • 1
    P

    See comments in /*!< */

    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            if(s.empty()) return true;  /*<! This should return true */
            unordered_set <string> unmatch;
            unordered_set <string> match;
            return helper(s, dict, unmatch, match);
        }
    private:
        bool helper(string s, unordered_set<string> &dict,unordered_set<string> &unmatch, unordered_set<string>&match){
            if(s.empty()) return true;
            if(dict.find(s)!=dict.end()) {  /*!< Simple base case you forget to test */
                match.insert(s);
                return true;
            }
            bool flag = false;
            for(int i=1; i<s.length(); i++)
            {
                string prefixstr=s.substr(0,i); 
                //prefixstr cannot be empty;
                //check prefixstr
                flag = false;  /*<! you forget to reset the flag in each iteration */
                if(!unmatch.count(prefixstr))
                {
                    if(match.count(prefixstr))
                        flag=true;
                    else
                    {
                        flag=helper(prefixstr, dict,unmatch, match);
                        if(flag)
                            match.insert(prefixstr);
                        else
                            unmatch.insert(prefixstr);
                    }           
                }
                // check suffixstr
                if(flag)
                {
                    string suffixstr=s.substr(i); /*!< by your design, suffixstr will never be empty */
                    //suffixstr could be empty
                    if(!unmatch.count(suffixstr))
                    {
                        if(match.count(suffixstr))
                            return true;
                        else
                        {
                            flag=helper(suffixstr, dict,unmatch, match);
                            if(flag) {
                                return true;    
                                match.insert(suffixstr);
                            }
                            else
                                unmatch.insert(suffixstr);
                        }
                    }
                }
            }
            return false;
        }
    };

  • 0
    W

    Thanks for the comments by Porker2008.
    I found and fixed several other issues. Here is the accepted code. This solution takes 36ms.
    Note that this solution has considered both "unmatched set" and "matched set", while most other solutions only consider one set.
    I did not use MIN and MAX of the dict, considering the real application scenarios: a) dict is usually very big, it is costly to calculate MIN and MAX. Idealy, MIN and MAX should be updated offline. b)the MIN of dict usualy is 1 and the length of input usually is not very long (therefore MAX is not very important).

       class Solution {
        public:
            bool wordBreak(string s, unordered_set<string> &dict) {
                // IMPORTANT: Please reset any member data you declared, as
                // the same Solution instance will be reused for each test case.
        		if(s.empty()) return false;
        		unordered_set <string> unmatch;
        		unordered_set <string> match;
        		return helper(s, dict, unmatch, match);
            }
        
        private:
        	bool helper(string s, unordered_set<string> &dict,unordered_set<string> &unmatch, unordered_set<string>&match){
        		if(s.empty()) return false;
        		bool flag = false;
        		if(dict.count(s)) {match.insert(s);return true;}
        		for(int i=1; i<s.length(); i++)
        		{
        			flag=false;/*!I forgot this */
        			string prefixstr=s.substr(0,i); 
        			string suffixstr=s.substr(i);
        
        			if(!(unmatch.count(prefixstr)||unmatch.count(suffixstr)))
        			{
        				if(match.count(prefixstr)) flag=true;
        				else
        				{
        					if(dict.count(prefixstr)) flag=true; /*!I forgot this */
        					if(flag) match.insert(prefixstr);
        					else unmatch.insert(prefixstr);
        				}
        				// check suffixstr
        				if(flag)
        				{
        					if(match.count(suffixstr)) return true;
        					else
        					{
        						if(dict.count(suffixstr)) return true; /*!I forgot this */
        						else flag=helper(suffixstr, dict,unmatch, match);
        						if(flag) return true;
        						else unmatch.insert(suffixstr);
        					}
        				}
        			}
        		}
        	}
        };
    

  • 0
    W

    Porker2008, really appreciate for your time and investigation on my design. As I posted above, besides what you have found out, there are several other issues in my code :(.


Log in to reply
 

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