0

In my check function I keep getting true (word is in dictionary) for some words which I did not load into the dictionary.

 bool check(const char *word)
    {   
        node *current = &root; // point to root
        for (int i = 0, n = strlen(word); i < n; i++)
        {
            int leaf = 0; //used to find if node exists
            if (isalpha(word[i]))
            {
                leaf = ((tolower(word[i]) - 'a') % (CAP-2)); //0-25
            }
            else if ( word[i] == '\'')
            {
                leaf = 26; //apostrophe
            }

---->--->-->if (current->next[leaf] != NULL)
            {   
                current = current->next[leaf]; //move deeper
            }
        }

        if (current->word == true) //checks if word
        {   
            return true;
        }
        else
        {
            return false;
        }
    }

The above function incorrectly identifies "make", for example, as a word in the dictionary. I think that's because i wait until the end to determine if its actually a word but I don't know why there is a true in the word field, especially since I set all the word fields to false after i calloc() a node.

I found if I return false immediately after hitting a NULL

if (current->next[leaf] != NULL)
    {   
        current = current->next[leaf]; //move deeper
    }
    else
    {
       return false;
    }

then the functions works properly. as far as check50 is concerned.

Why does the first function incorrectly identify a word when it's not actually in the dictionary?

0

That's because if you don't include the else case, and current->next[leaf] is NULL, on the next iteration of the for loop you will still be at the same node of the trie.

Say we have the the following in our trie:

[w] -> [e] -> [d] -> [d] -> [i] -> [n] -> [g]

so we have saved just the word wedding.

Now with your code, if we search for weed:

  1. We start at root, the pointer for w is not NULL, so we move to this node.
  2. Now the pointer for e is not NULL so we move to this node.
  3. Now the pointer for e is NULL, so we don't move to another node, we stay at the node e we were at the beginning of this loop.
  4. Now the pointer for d is not NULL, so we move to this node.
  5. And now the letters have finished, so the word weed was in the dictionary. Right?

As you correctly guessed and foxed your code, you have to return false as soon as you realize that the next letter in the word is not in the trie.

Also, out of curiosity, what does % (CAP-2) do?

Happy Coding!

2
  • Thank you. I don't remember why i included it but i think it's so i don't go over 25
    – NovNov
    Jun 20 '17 at 20:49
  • Since you have already checked that it is a character in the alphabet, and you have converted it to lowercase, do you really need to take the modulo? Think about it.
    – ChrisG
    Jun 20 '17 at 22:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .