Trie Data Structure - Beau teaches JavaScript
video description
Date: 2022-03-14
Related videos
Comments and reviews: 7
Shini1984
I'd like to offer a suggestion: when adding a word, you use substring. There are two problem with this approach. 1. Substring iterates over a string in O(n) time. 2. Substring creates a copy of the string (because it is immutable). So it needs O(n) time for each iteration and O(n - 1) = O(n) space for each iteration, which makes it O(n-2) time and space complexity when adding.
I suggest using an array (word.split(--)) and passing around both the array itself and current index when adding the word. Benefits: we don't do substring, we simply iterate index by one. Both of these are done in O(1) time and don't use any extra space.
Other than that I'd use while loop to iterate over the the nodes instead of using recursion. This allows us not to worry about recursion stack overflowing (which may or may not become an issue in the long run).
I realize this is a 3 year old video, I'm just hoping someone will find this useful, as I found this video quite useful for understanding Tries and how to implement them in JS.
Thanks for the explanation! It may not be perfect, but it is quite useful.
reply
I'd like to offer a suggestion: when adding a word, you use substring. There are two problem with this approach. 1. Substring iterates over a string in O(n) time. 2. Substring creates a copy of the string (because it is immutable). So it needs O(n) time for each iteration and O(n - 1) = O(n) space for each iteration, which makes it O(n-2) time and space complexity when adding.
I suggest using an array (word.split(--)) and passing around both the array itself and current index when adding the word. Benefits: we don't do substring, we simply iterate index by one. Both of these are done in O(1) time and don't use any extra space.
Other than that I'd use while loop to iterate over the the nodes instead of using recursion. This allows us not to worry about recursion stack overflowing (which may or may not become an issue in the long run).
I realize this is a 3 year old video, I'm just hoping someone will find this useful, as I found this video quite useful for understanding Tries and how to implement them in JS.
Thanks for the explanation! It may not be perfect, but it is quite useful.
reply
sha
Thanks a lot sir, really wounderful , i have a DS question for you , please help me ......Have one DS question, need anser.
Q : we have a city , in which we have locations, each location has few restaurents.
One ( ex: KFC) restaurent might be in multiple locations( like HiTechcity, Nampally etc).
To Given restaurent get all its locations, given location display all restaruents in that location.
What Data Structure use this problem?
reply
Thanks a lot sir, really wounderful , i have a DS question for you , please help me ......Have one DS question, need anser.
Q : we have a city , in which we have locations, each location has few restaurents.
One ( ex: KFC) restaurent might be in multiple locations( like HiTechcity, Nampally etc).
To Given restaurent get all its locations, given location display all restaruents in that location.
What Data Structure use this problem?
reply
Justin
What about -Do- you never printed it out or showed us how you know when you've come to the end of a word that could be a part of a longer word. Do and then Done Done prints because it is the end of the branch and has no children but Do, has children and therefor does not get printed out.
reply
What about -Do- you never printed it out or showed us how you know when you've come to the end of a word that could be a part of a longer word. Do and then Done Done prints because it is the end of the branch and has no children but Do, has children and therefor does not get printed out.
reply
MM
Cool video. You can make the -add- function a bit simpler by removing the -else- and the return statement above it. Because both return statements around -else- are doing the same thing.
reply
Cool video. You can make the -add- function a bit simpler by removing the -else- and the return statement above it. Because both return statements around -else- are doing the same thing.
reply
aylictal
just fyi in your isWord return you're returning a boolean ternary which is an antipattern.
you can simply call return node.keys.has(word) && node.keys.get(word).isEnd()
reply
just fyi in your isWord return you're returning a boolean ternary which is an antipattern.
you can simply call return node.keys.has(word) && node.keys.get(word).isEnd()
reply
Doug
Thanks very helpful! Isn-t substring a O(n) operation though? That means search operations are increased from O(n) to O(n-2), since you create a new string for each iteration
reply
Thanks very helpful! Isn-t substring a O(n) operation though? That means search operations are increased from O(n) to O(n-2), since you create a new string for each iteration
reply
itech
In -isWord-, you could also have used -node- as the second parameter, just like in -add-, right?
Very good explanation tho, thank you!
reply
In -isWord-, you could also have used -node- as the second parameter, just like in -add-, right?
Very good explanation tho, thank you!
reply
Add a review, comment
Other channel videos
