"a" ["a"] wrong answer, but I get the right answer in VS2010


  • 0
    S

    class Solution
    {
    public:

    bool wordBreak(string s, unordered_set<string> &dict)
    {
        if(s.length() == 0)
    	{
    		return true;
    	}
    	int flag = myWordBreak(s, dict, 0);
    	if(flag > 0)
    	{
    	    return true;
    	}
    	else
            return false;
    }
    
    int myWordBreak(string s, unordered_set<string> &dict, int f)
    {
        int flag = f;
    	if(s.length() == 0)
    	{
    		return flag;
    	}
    
    	for(int i = 1; i <= s.length(); i++)
    	{
    	    flag = 0;
    		string word = s.substr(0, i);
    		unordered_set<string>::iterator iter = dict.find(word);
    		if(iter == dict.end())
    		{
    			continue;
    		}	
    		else
    		{
    			for(int j = i; j < s.length(); j++)
    			{
    				string suffix = s.substr(i, j-i+1);
    				iter = dict.find(word + suffix);
    				if(iter != dict.end())
    				{
    					flag = 1;
    					continue;
    				}
    				else
    				{
    					string remainder = s.substr(j);
    					return myWordBreak(remainder, dict, flag);
    				}
    					
    			}
    		}
    	}
    	
    	return flag;
    }
    

    };


  • 0
    M

    With the answer you've given, the problem is as follows:
    myWordBreak("a",{"a"},0) gets called from the starting method, and since s is not an empty string, it reaches the for loop.

    i = 1, which is equal to s.length(), so enters the loop. Flag is 0 and iter returns that word is in the dict, so the else is entered. However, j=i=1, which is not less than s.length, so the inner loop is skipped. i increases, so it is greater than the length, skipping the outer loop and returning flag, which has never been set, so is still 0. Therefore, the algorithm returns false.

    The problem occurs whenever the string s is equal to the string word. In order to fix this, I suggest an else if after the "Is the word in the dict" check t return true if the length of word is equal to the length of s.

    if(iter == dict.end())
        {
            continue;
        }  
    else if (i == s.length){
        flag = 1; //or just return 1;
    }
    

    As a side note, I'm pretty sure your algorithm will get a TLE as it is currently written. I suggest you store whether a given string can be broken when you discover it, and use that information to skip quite a bit of calculation.

    Also, your inner for loop tacks on longer and longer suffixes to the end of the word, seeing if they are also in the dictionary. However, as soon as the first extension fails, it returns the result. For example, "singingchoir", {"sing","singing","choir"}. word works until it gets "sing", then attempts to extend it. suffix, on its first loop, checks adding "i", resulting in "singi", which returns dict.end(). Therefore, the else condition runs. "ingchoir" gets passed into the function, returning false, which then returns through the function instead of continuing on to "singing" and finding the proper break.


Log in to reply
 

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