Implement Trie (Prefix Tree) - Leetcode 208
Vložit
- čas přidán 9. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
Coding Solutions: • Coding Interview Solut...
Dynamic Programming Playlist: • House Robber - Leetco...
Tree Playlist: • Invert Binary Tree - D...
Linked List Playlist: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/implemen...
0:00 - Read the problem
1:53 - Drawing Explanation
11:40 - Coding Explanation
leetcode 208
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#trie #prefix #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
This is the best Trie introduction video I watched in youtube, very clear and concise. Bravo!
Never thought Trie would be this easy to understand, thanks a lott!!
You legitimately explain these concepts better than any professor I've had, and I went to one of the most highly regarded schools in the US for Computer Science. You outdid both the professors and their teaching assistants.
You have a gift for explaining this stuff.
Neetcode really saving the day here. I watched other videos, but none explained and illustrated how to code it efficiently. Your drawing is so helpful and the clean, simple code makes sense. Thanks Neet!
I avoided trie for so long thinking it will be difficult to understand. Thanks for this. This was very easy.
I am with you on this, hahaha
Thank you so much! Just can’t tell how cool and valuable your videos are! Keep’em coming!
never thought that I would get the best trie introduction video in a leetcode video. Thanks for the great work!
A note on implementation: instead of a python class representing the node, you can simply represent each node as a dictionary of chars to dictionaries and use a placeholder (like '$') to mark the end of a word. This will be more efficient (same big-O, though) in python in both memory and time, for you are not wasting a bunch of space pre-allocating lists, you are not having to deal with python's overheads and, most importantly, you would be using a highly optimized python data structure calling c under the hood. On top of all of that, you get a cleaner implementation
Thank you so much!! I have learnt a new data structure today..
Man your videos are incredible, and I've learned so much about programming in general just from your channel. Before this I was stunned about how to approach problems like this or dynamic programming but just from following solutions and understanding the concepts better I can do problems like this moderately well now
Always love the way you explain things so easily and concisely.
This is the best Trie vid so far ! Excellent explaination . 👍
Best explanation of Tries I have come across so far. Bravo!
You are literally making my life easy. Thanks man 🙏🏻
Omg this is amazing, I have been trying to understand this for an hour now - finally I get it! Thanks!
Simplest video to understand Trie and implement it. Keep up the good work.
I haven't seen better tutorials than yours for LC problems anywhere! Great work :)
Thank you! Your explanation of of the trie data structure is so clear!
These videos are literally better than the courses I took in University. Thank you!
honestly just want to say your videos been great in my interview prep :) (totoal newbie at leetcode)
Thank you very much for clear explanation and truly neat code :)
Thank you!! I had never seen tries and had been avoiding it. Its actually quite easy.
You are the best leetcode teacher on entire CZcams!
You are a godsend. Thank you sooooooo much for all your work 🙏🙏
A Big Salute To You Bro, for the solutions and great explanation , I have recommended this channel to at least more than 3 people 🙌
Thank you, the best trie explanation! You're amazing!!!
I had no other option but to like this implementation! Thanks Kevin :)
Amazing explanation, great job!
thank you so much! such an awesome explanation of Trie you make everything so easy to understand thanks!!
Thank you so much. Your videos makes everyday learning a feasible plan. Your explanation makes every single problem lots more easier to understand and reduce my imagination to the difficulty of the problem.
Thank you very much for the very clear explanation!!!
Excellent video, as always.
Great explanation! thank you :)
OMG, man, you possess a special talent to explain complicated things smoothly and simple. I'm a big fan of your channel!
Very well explained. Thanks!
You are always the best!
Excellent explanation!! thank you a lot!
Awesome explanation my man!
This was one of the more enjoyable problems I've done
Super helpful videos. Been looking at them a lot.
Thank you so much 🙏
Beautifully explained 👏🏻👏🏻👏🏻
Good explanation. After understanding the logic I implemented the code myself. Feels good.
Brilliant! Thank you so much!
What an amazing explanation for the guy who just started learning tries 👍
Great explanation! The very important take away here was that you mark the end of a valid word with the TrieNode variable, otherwise "appl" may look like a valid word after inserting "apple"
When I did this one before wathcing the video, my code was double the length of yours. Nice solve!
Real cool explanation, Thanks Man.
Great practical explanation of Trie!!
Thank you! Great video
Dude i have been postponing this DS for an year thinking its going to be very tuff. U just confirmed it to be wrong in first ten mnts. Great job man!
a great explanation !. Thanks
please explain time and space complexity after u solve the problem
Time is O(n*m) for insertion (n is the number of words, m is the max len), O(m) for search. Space is O(n * m)
The code is marvelously simple considering how useful of a data structure this can be.
Loved the easy to understand explanation. 🧡 from remote.
You’re awesome dude ty
Brilliant explanation
Amazing explanation
really helpful thank you so much.
Great simple explanation
thanks! I thought Trie is gonna be super hard, nice explanation
Using a hash map was genius. Once I saw that, I went and redid my code before looking at the rest of ur solution
Nice explanation!
Great explanation
Thanks Man!
crisp and clear
Excellent explanation
Neat video! Please do a video on Design Search Autocomplete System.
I have watched a few explanations on the tries, this is the best. Keep them coming at least for now you don't have a job
dude he is in google !..
someone truly said.
Time is mightier than fate..
@@TechOnScreen Yah, I knew with his level of skills its just a matter of time and he will get one of those top jobs in the industry
@@antonyndungu5514 yeah dude.. hope some day we will have our luck too 😂
@@TechOnScreen True, can't wait for that :-)
Thanks!
great video!
skimmed through 3-4 blah blah videos, this finished the job gracefully
brilliant!
Awesome!
The best Trie Explanation
If you could have explained all the data structures like this before, My life would have become easier..
But did you come earlier to get his help is the question that I want to ask from you ?
neatly implemented
A more useful and challenging problem would be to return a list of words that starts with a given prefix. Pretty much autocomplete. I’m not sure if that one can be solved iteratively though, I’ve only seen it done recursively.
yess!! tries are cool
Very helpful
good job
My favorite data structure, I just came to make sure my code was as good as the one you show, and its exactly the same thankfully. Thanks for your videos
Liked!
Can you code up the delete functionality as well ?
helpful video
After your explanation I was able to code it in under 2 mins without looking back at the video. You sir are an absolute legend.
Thanks
It should be mentioned that marking Apple as the end of the word is not just to be safe. Your function would return false for not found if your word search was searching for both Apple and Apples if you didn't have that boolean to check if it was the end of the word. If Apples existed for example, then the E in Apple would no longer be the end of the chain. Despite that fact, Apple is a very legitimate word even though it has a child node in 'S'.
when you enter apple, it will mark e as the end of the word, then again when u enter apples, it will run for the length of apples, and add s after e. Then if u search, u will get True for both. Just because a node is marked end = True doesnt mean u cant access or add to that Node.
this guy is making our life play on easy mode
you are the best
Keep doing more videos
you don't need to create additional TrieNode class, just initialize everything in TrieNode class into Trie class.
and replace every cur = self.root by cur = self and it works fine
i don't know why, this new solution was much faster, may be it was leetcode bug
Hey, what if we insert a substring of an already existing string. Say we insert 'app' when 'apple' already exists in the Trie. Wouldn't that make the second 'p' in the 'apple' also an 'endOfWord' making the 'le' in 'apple' inaccessible?
No harish, because you will only be checking for the endOfWord condition when you have reached the end of the particular word you are searching for, say you are searching for apple and both the second p and the e are marked as endOfWord, then when you are searching for apple, you iterate one by one, a, p, p, l, e and after reaching the end point, only then you check for the endOfWord Condition. In case you are searching for app, then you iterate through a, p, p and then check whether the currentNode has endOfWord as true, in this case yes, so both app and apple are accessible.
@@kamaleshs5324 that doesn't answer the question though, since he asked what will happen if "we insert a substring of an already existing string"
No, it will not be inaccessible, simply because if you look again at the search function you will see the for loop runs down the tree for the length of the searched word REGARDLESS of if it finds a node with EndOfWord.
Only AFTER it has gone down the length of the word, will it check if the node it LANDS on is EndOfWord=True.
I.e it will NOT stop just because it found an EndOfWord, but instead traverse the word's chars entirely and then check if the node it lands on is EndOfWord=True
Do we have to use trieNode? I used dictionary and had "None" to mark if the node is at the end.
Perfect
Sir i have a doubt that in apple it's two p's and since we inserted the first so will it insert the second one?? Plzz explain
Data structure look like for letter apple :
{"a":{"p":{"p":{"l":{"e:{}}}}}
U a God
My assumption for runtime complexity is O(n) where n is the number of characters in the string that we are inserting or searching for. Now for space complexity, it seems to me that it is O(n^n) because each node can have n children.
not n nodes can have n children, you can say, 26 chars can have n children :) That Means, O(n+m+k+.........26th l)
@@hillarioushollywood4267 So this is Space: O(n * 26) where n is the length of our word and each character in our word can have 26 children max
I like this one
Very good explanation, but can someone tell me which way is more efficiency(if we dont care space)
on above case, Trie, or a hashmap include all combination app become a = [app], ap = [app], app = [app], and 1 more hash for just store the word, as latter way can ensure search and startwith run O(1) time?
Yes, you can achieve average O(1) for searching and startsWith this way, though your insert will be slower. For a word of length m, I believe it'll be be O(m^2): you'll be adding m strings, obtaining those through list slicing, which is O(slice length). Average slice length is about half the length of the word in this case (for a word of length 4: 1st prefix is length 1, second is 2, third is 3, last is 4), so m * m * ~0.5, which is O(m^2). Doing it this way could be better if you inserted rarely, but searched and used startsWith a lot. You said not to care about space, but this is more space-efficient as well as a hashset is a built-in optimized data structure, while a TrieNode is an entire user-defined class instance.
I love you bro