cfunctionif-statementlogical-operatorstrie

CS50 Trie Week 5: check function not working


I have been trying to complete the trie practice problem from the CS50 course. The check function that I wrote must check whether the user input is found within the trie that has been created in the main function.

bool check(char* word)
{
    node *temp = malloc(sizeof(node));
    temp = root;

    for (int i = 0; i < strlen(word); i++){
        int ix = tolower(name[i]) - 'a';
        if (ix < 0 || ix => SIZE_OF_ALPHABET){
            return false;
        }
        if (temp->children[ix] == NULL && temp->is_word == false){
            return false;
        }
        temp = temp->children[ix];
    }
    return true;
}

The program compiles and runs just fine, however, whenever I deliberately input an invalid name that should not be found, the program still outputs that the name has been found, which should not happen. Could someone please explain what my mistake is? Thanks in advance.


Solution

  • Firstly the function should be declared like

    bool check( const char *word );
    

    because passed strings are not changed within the function.

    The function produces a memory leak in this code snippet

    node *temp = malloc(sizeof(node));
    temp = root;
    

    That is at first memory was dynamically allocated and its address was assigned to the pointer temp and then the pointer was reassigned. So there is no possibility in this case to free the allocated memory.

    Actually neither memory should be allocated.

    Using the function strlen is redundant.

    As for your question then in this if statement

    if (temp->children[ix] == NULL && temp->is_word == false){
    

    instead of the logical AND operator there must be the logical OR operator

    if (temp->children[ix] == NULL || temp->is_word == false){
    

    The function can look the following way

    bool check( const char *word )
    {
        bool present = root != NULL && *word != '\0';
    
        for ( node *temp = root; present && *word; ++word )
        {
            present = isalpha( ( unsigned char )*word );
            
            if ( present )
            {
                int ix = tolower( *word ) - 'a';
    
                present = ix < SIZE_OF_ALPHABET && temp->children[ix] != NULL && temp->is_word;
    
                if ( present ) temp = temp->children[ix];
            }
        }
    
        return present;
    }