In this exercise, we will work on the count_prefix() method in our Trie class. As its name suggests, this function will count the number of words with a prefix up to some character. We track this count in the freq variable of a TrieNode.
Consider this example of a trie that contains the following words:
- ADD
- ADDITION
- ADDENDUM
- ADVERTISEMENT
- ADVANCED
- APPLE
The freq variable in the node for character ‘A’ will be set to 6 since all six words have a prefix ‘A’. Node ‘D’ will have freq set to 5 because five words have the prefix “AD”. The second node ‘D’ will be set to 3. Node ‘V’ will have freq set to 2 because only two words have the prefix ADV. The counter in Node ‘P’ will be set 1 because of APPLE.
The algorithm for this process is the same algorithm as that for search_string(). The only difference is that count_prefix() will return the value of the last character’s freq variable instead of returning the value of the end_of_key variable.
Instructions
Inside count_prefix(), complete the looping that will search the trie for the prefix.
At the end of the loop, the pointer will be pointing to the last character in the prefix. Return this character’s counter.