I am trying to implement a trie in Python, given the list where * is used to represent the end of a word only if there are other letters within its node.
For example, given the following list, [sammie, sammy, sam, sadly, funny, fun], the trie would look like this:
|s|f|
/ \
|a| |u|
/ \
|m | d| |n|
/ \ \
|m | #| sadly |n | #|
/ \ / \
|i | y| sam funny fun
/ \
sammie sammy
So far my code returns a dictionary where the word is always listed until the last letter (including the terminal node *) even if it is the only word that can be possibly made from the letters. (Ex. sadly's last parent node should be d, as no other words can be made from those letters). I'm wondering how I can implement these cases and how I can save the values as nodes in Trie() without adding a node class.
Here is my code and what it is currently outputting:
class Trie:
def __init__(self):
self.d = {}
def insert(self,word):
current = self.d
for char in word:
if char not in current:
current[char] = {}
current = current[char]
current['*'] = word
return self.d
output:
{'s': {'a': {'m': {'m': {'i': {'e': {'#': 'sammie'}}, 'y': {'#': 'sammy'}}, '#': 'sam'}, 'd': {'l': {'y': {'#': 'sadly'}}}}}, 'f': {'u': {'n': {'n': {'y': {'#': 'funny'}}, '#': 'fun'}}}}
Aucun commentaire:
Enregistrer un commentaire