In this exercise, we will search for a string in a trie. A string is loaded into a trie for one of two reasons:
- The trie represents a dictionary of words.
- The string contains some relevant information.
The function search_string()
in our Trie
class will search the trie for the string and return whether it is there or not. We can modify this function to return relevant data associated with the string, but for our purposes, we will only determine whether the string is in the trie or not.
Here are the steps of the algorithm to search for a string:
- Initialize a pointer to the root node in the trie.
- Create a loop that will loop through all the characters of the string passed into
search_string()
. - Access the current node’s
nodes
dictionary and attempt to retrieve the node associated with the current character.- If the node exists, set the pointer to this node.
- If the node does not exist, that means this string is not there; therefore, the loop should terminate immediately, and
search_string()
should returnFalse
.
- Assuming the word exists, the loop will repeat this process for all remaining characters.
- At the end of the loop, the pointer points to the node associated with the last character in the string; therefore, the function should return the value associated with
end_of_key
.
Please note that we return the value of end_of_key
and not True
because we want to know if this string is a full entry. A string may exist in the trie only because it is the prefix to a longer string. In that case, we should return False
because the string has not been entered as its own word.
Let’s take a look at an example. We have a trie that contains the word CODECADEMY.
We will search this trie for the word CODE (this word has not been entered into the trie):
- Initialize a pointer to the root node.
- A loop will loop through all characters of CODE.
- We will access the root node’s
nodes
dictionary to retrieve the node associated with the letter ‘C’. - We will set the pointer to that node.
- Repeat steps 2 through 4 for the remaining characters.
- This loop will not terminate early because the string CODE exists in the trie as a prefix of CODECADEMY.
- After the loop terminates, the pointer will point to the node associated with the letter ‘E’.
- Return the value of the
end_of_key
variable of the node associated with the letter ‘E’. This will beFalse
because CODE does not exist in the trie as its own word.
If you search for the word CODECADEMY, search_string()
will return True
.
If you search for the word COCOA, search_string()
will terminate early and return False
because there is no node associated with the second ‘C’.
If there is relevant information associated with the word, it will likely be stored as a field in one of the TrieNodes
. If you want that, have search_string()
return it!
Instructions
Inside search_string()
, initialize a pointer to the root node of the trie. Call this pointer nxt2
.
Complete the loop that will loop through the characters of the string string
and searches the trie for these characters in order.
Click the hint if you need any more guidance.
It is possible that the string you are searching for has never been entered into the trie. In this case, have the function return False
.
Once the loop has finished going through all the characters, have the function return a boolean value regarding whether or not the string has been entered into the trie.