https://forum.freecodecamp.org/t/please-help-in-trie-fix-issue/572090
What is the issue? And what challenge is this?
please help me in this trie data structure getting the all words with prefix are not correct
I can’t read code when it is inside an image.
Please post actual code if you need to get someone to read it.
Also please clarify what it is you need help with. I’m still not understanding.
Key = TypeVar("Key")
@dataclass
class TrieNode(Generic[Key]):
key: Optional[Key]
parent: Optional[TrieNode]
children: dict[Key, TrieNode] = field(init=False, default_factory=dict)
is_terminating: bool = field(init=False, default=False)
class Trie(Generic[Key]):
def __init__(self):
self.root = TrieNode(key=None, parent=None)
def insert(self, collection: str) -> None:
current = self.root
for element in collection:
if element not in current.children:
current.children[element] = TrieNode(key=element, parent=current)
current = current.children[element]
current.is_terminating = True
# Support the "in" operator
def __contains__(self, collection: str) -> bool:
return self.contains(collection)
def contains(self, collection: str) -> bool:
current = self.root
for element in collection:
child = current.children.get(element, None)
if not child:
return False
current = child
return current.is_terminating
def remove(self, collection: str) -> None:
current = self.root
for element in collection:
child = current.children.get(element, None)
if not child:
return
current = child
if not current.is_terminating:
return
current.is_terminating = False
while current.parent and not current.children and not current.is_terminating:
parent = current.parent
parent.children.pop(current.key)
current = parent
def collections_starting_with_prefix(self, prefix: str) -> list[str]:
current = self.root
for element in prefix:
child = current.children.get(element, None)
if not child:
return []
current = child
return self.collections_starting_with_prefix_after_node(prefix, current)
def collections_starting_with_prefix_after_node(
self, prefix: str, node: TrieNode
) -> list[str]:
# 1
results: list[str] = []
results.append(prefix)
# 2
for child in node.children.values():
if child.key:
prefix += child.key
results.extend(
self.collections_starting_with_prefix_after_node(prefix, child)
)
return results
if __name__ == "__main__":
trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("card")
trie.insert("care")
trie.insert("cared")
print(trie.collections_starting_with_prefix("car"))
when I search words with perfix this shows wrong words
correct result is [“car”, “card”,“care”, “cared”].
but it shows wrong result [“car”,“card”,“carde”,“carded”]
I want words of a string with help of the collection_start_with_prefix method but when run the code it fetches the wrong words which I did not insert in the trie
it shows the [‘car’, ’ card’, ‘carde’, ‘carded’] but the correct one is [‘car’, ‘card’, ‘care’, ‘cared’] with a prefix search, I want to know why this code fetches the wrong string of words.
def collections_starting_with_prefix(self, prefix: str)
this method is not show correct result
Please reply to me if you check my code
Please help me. My code is trying to accomplish search all strings of words with prefix matching but it shows the wrong result with ‘car’ prefix search. the correct result is [“car”, “card”, “care”, “cared”].
but it shows the wrong result [“car”,“card”,“carde”, “carded”]
I still don’t understand you.
You said you are trying to find words that start with ‘car’
All these words that you said are wrong all start with car.
I inserted only these words then it should be show these words [‘car’, ‘card’, ‘care’, ‘cared’] with car prefix
trie.insert(“cat”)
trie.insert(“car”)
trie.insert(“card”)
trie.insert(“care”)
trie.insert(“cared”)
but shows [‘car’, ‘card’, ‘carde’ , ‘carded’]
why this shows ‘carde’ and ‘carded’ which I did not inserted in trie.
only two words are wrong which I did not insert in trie ‘carde’, and ‘carded’
can you provide a working version of your code in replit?
this is my working code repl linkhttps://replit.com/@murtaza63/Trie-Data-structure#main.py
1 Like
So I played with the code a bit to try to understand what was happening.
I removed the inserts and used exactly 2
cat
car
I noticed that the structure you were creating essentially makes this type of tree
c at the top
a below that
t & r children of a together
Then I modified the prefix to be a simple ‘c’ and searched for that
and I got the result
[‘cat’,‘catr’]
The reason seems to be the function
collections_starting_with_prefix_after_node
This part of the code finds all the children and appends them to the prefix
so you end up with catr because t and r are both children of a
So try to figure out what you should be doing instead of just blindly adding all the children to the prefix
Thanks for your reply and help me but I am confused about that what should be changed in this code for child in node.children.values(): if child.key: prefix += child.key
so it can work properly.
you are adding all the children so that is giving you the wrong result
you have to find a way to split the children up into different words I guess
so that instead of getting
[“cat”,“catr”]
you get
[“cat”,“car”]
First thing would be to stop blindly adding all the children to the prefix I would guess.
Perhaps you have to check if the child is the terminating node and if it is, you have to somehow reset so that the next child gets added to a different prefix?
Not sure really.
Thanks so much with the help of your advice issue is solved
1 Like
This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.