Learn

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 `Trie`.
• Iterate through the characters of the `string` parameter using a loop.
• Take the first character and call the `root` node’s `add_char()` method passing in the character as a parameter.
• The `add_char()` method processes the character according to its logic.
• The `add_char()` method then returns the node associated with the current character.
• The pointer will now point to the node returned from `add_char()`.
• Before the loop continues, the returned node associated with the character has a `freq` variable that is keeping track of the number of prefixes up to this character. `freq` is 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 `end_of_key` set to `True` to 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:

1. We call `add_word(CODE)`.
2. Inside `add_word()`, we initialize a pointer to the `root` of the trie.
3. A loop is created that will iterate through “CODE”.
4. We will call `root.add_char('C')`.
5. The `root.add_char()` function will create an entry in the `root` node’s `nodes` dictionary if one does not already exist.
6. `root.add_char()` will return the node that is associated with the character ‘C’.
7. We set the pointer to this node.
8. We increment the `freq` variable by one to represent that this node (this character) is part of `freq` amount of prefixes.
9. The loop proceeds on to the next letter ‘O’ and repeats steps 2-9 for the remaining characters.
10. In the end, the node representing the character ‘E’ will have its `end_of_key` variable set to `True`.

Let’s implement this algorithm in the `add_string()` method!

### Instructions

1.

Inside the `add_string()` method, initialize a pointer to the `root` node and call it `nxt`.

CLick the hint if you get stuck.

2.

Loop through the characters of `string` (the string parameter that is passed into `add_string()`) and add them to the trie.

3.

The `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:

The `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.

4.

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.