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.