In this exercise, we will describe the algorithm that adds a word to a trie. We will then implement this algorithm in the
add_string() function of the
Trie class. We will be implementing this algorithm iteratively.
Let’s go over the algorithm to add a string to a trie step-by-step:
- Begin by creating a pointer that initially points to the root node of the
- Iterate through the characters of the
stringparameter using a loop.
- Take the first character and call the
add_char()method passing in the character as a parameter.
add_char()method processes the character according to its logic.
add_char()method then returns the node associated with the current character.
- The pointer will now point to the node returned from
- Before the loop continues, the returned node associated with the character has a
freqvariable that is keeping track of the number of prefixes up to this character.
freqis now incremented.
- The loop repeats this process for the remaining characters.
- The very last node, representing the last character in the string, will have its
Trueto indicate that this is the end of a string.
To review this, let’s take a look at an example. We wish to add the word “CODE” to the trie:
- We call
add_word(), we initialize a pointer to the
rootof the trie.
- A loop is created that will iterate through “CODE”.
- We will call
root.add_char()function will create an entry in the
nodesdictionary if one does not already exist.
root.add_char()will return the node that is associated with the character ‘C’.
- We set the pointer to this node.
- We increment the
freqvariable by one to represent that this node (this character) is part of
freqamount of prefixes.
- The loop proceeds on to the next letter ‘O’ and repeats steps 2-9 for the remaining characters.
- In the end, the node representing the character ‘E’ will have its
end_of_keyvariable set to
Let’s implement this algorithm in the
add_string() method, initialize a pointer to the
root node and call it
CLick the hint if you get stuck.
Loop through the characters of
string (the string parameter that is passed into
add_string()) and add them to the trie.
freq variable in this node represents the number of words that contain the prefix up to this character. Since a prefix was just added, modify the
freq variable to represent this addition.
As an example, consider a trie containing the following words:
freq variable in the nodes ‘A’, ‘D’, and ‘D’ will be set to 3 because there are three words that contain the prefix ADD.
A word counts as its own prefix.
After the loop has completed entering the string into the trie, set the last node’s (character’s)
end_of_key variable to
True which represents that this character is the end of a word.