Let’s define the TrieNode
class we will use to implement a trie.
To represent subsequent characters in a string, a TrieNode
object contains a dictionary that maps a character to an instance of TrieNode
. This works somewhat like a linked list in which you have a node that contains information and a pointer to another node.
We represent the TrieNode
as the following clas:
class TrieNode: def __init__(self): self.nodes = {}
The self.nodes
field is a dictionary that contains the mapping of each character and its subsequent node mapping.
TrieNode
also contains a function used to append a character:
class TrieNode: def __init__(self): self.nodes = {} def add_char(c: chr) -> TrieNode: if c not in self.nodes: self.nodes[c] = TrieNode() return self.nodes[c]
We call this method from the Trie
class. It returns a TrieNode
because a loop in the add_word()
method will be responsible for iterating through the nodes starting at the root
and placing the characters where they need to be. There are two possible scenarios:
- The current
TrieNode
already contains an entry for characterc
because it has been entered earlier as the prefix to another word. In this case,add_char()
retrieves theTrieNode
mapped toc
and returns it. - The current prefix has not been entered. Therefore,
TrieNode
does not contain a mapping for the characterc
. In this case,add_char()
creates a mapping and returns it.add_word()
will continue to load the word into the trie.
We can augment the TrieNode
class to hold other relevant information about a word.
Instructions
Modify the TrieNode
class to contain a field that represents whether or not a current character is the end of a word. Call this field end_of_word
, and add it to the __init__()
constructor.
Set end_of_word
to False
.
Modify the TrieNode
class to contain a field that will represent the number of times that this node has appeared in a prefix. Call this field freq
, and add it to the __init__()
constructor.
Set freq
to 0
.