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.
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;
}