Clean, slightly verbose C solution


  • 1
    S

    {

    bool IsInDictionary(char* Begin, char* End, char **Dictionary, int NumberOfWords)
    {
        int Index;
        bool Answer = false;
        bool Condition1 = false, Condition2 = false;
        int SubStringLength = End - Begin + 1;
        
        for (Index = 0; Index < NumberOfWords; Index++)
        {
            Condition1 = (SubStringLength == strlen(Dictionary[Index]));
            
            if (Condition1)
            {
                Condition2 = (strncmp(Begin, Dictionary[Index], strlen(Dictionary[Index])) == 0);
            }
        
            if (Condition1 && Condition2)
            {
                Answer = true;
                break;
            }
        }
        
        return Answer;
    }
    
    
    bool wordBreak(char* String, char** Dictionary, int NumberOfWords) 
    {
        bool CanBeBroken[strlen(String) + 1];
        char *StringBegin, *StringEnd;
        int PrefixStart, PrefixEnd;
    
        if (String == NULL)
        {
            return false;
        }
    
        StringBegin = String;
        StringEnd = String + (strlen(String) - 1);
    
        if (IsInDictionary(StringBegin, StringEnd, Dictionary, NumberOfWords))
        {
            return true;
        }
    
        CanBeBroken[strlen(String)] = true;
    
        for (PrefixStart = strlen(String) - 1; PrefixStart >= 0; PrefixStart--)
        {
            CanBeBroken[PrefixStart] = false;
                
            if (IsInDictionary(String + PrefixStart, StringEnd, Dictionary, NumberOfWords))
            {
                CanBeBroken[PrefixStart] = true;
                continue;
            }
            
            for (PrefixEnd = PrefixStart; PrefixEnd < strlen(String); PrefixEnd++)
            {
                if (CanBeBroken[PrefixEnd + 1] && 
                    IsInDictionary(String + PrefixStart, String + PrefixEnd, Dictionary, NumberOfWords))
                {
                    CanBeBroken[PrefixStart] = true;
                    break;
                }
            }
        }
    
        return CanBeBroken[0];
    }
    

    }


Log in to reply
 

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