🚀 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.

@niravarora9887

5 ай бұрын

I am with you on this, hahaha

never thought that I would get the best trie introduction video in a leetcode video. Thanks for the great work!

Thank you so much!! I have learnt a new data structure today..

Thank you so much! Just can’t tell how cool and valuable your videos are! Keep’em coming!

This is the best Trie vid so far ! Excellent explaination . 👍

Best explanation of Tries I have come across so far. Bravo!

Always love the way you explain things so easily and concisely.

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

Thank you! Your explanation of of the trie data structure is so clear!

Simplest video to understand Trie and implement it. Keep up the good work.

You are literally making my life easy. Thanks man 🙏🏻

honestly just want to say your videos been great in my interview prep :) (totoal newbie at leetcode)

Omg this is amazing, I have been trying to understand this for an hour now - finally I get it! Thanks!

I haven't seen better tutorials than yours for LC problems anywhere! Great work :)

Thank you very much for clear explanation and truly neat code :)

Amazing explanation, great job!

These videos are literally better than the courses I took in University. Thank you!

Thank you, the best trie explanation! You're amazing!!!

Thank you very much for the very clear explanation!!!

Super helpful videos. Been looking at them a lot.

@NeetCode

Жыл бұрын

Thank you so much 🙏

Thank you!! I had never seen tries and had been avoiding it. Its actually quite easy.

A Big Salute To You Bro, for the solutions and great explanation , I have recommended this channel to at least more than 3 people 🙌

You are a godsend. Thank you sooooooo much for all your work 🙏🙏

I had no other option but to like this implementation! Thanks Kevin :)

Great explanation! thank you :)

You are the best leetcode teacher on entire KZread!

Very well explained. Thanks!

Excellent video, as always.

Beautifully explained 👏🏻👏🏻👏🏻

thank you so much! such an awesome explanation of Trie you make everything so easy to understand thanks!!

Excellent explanation!! thank you a lot!

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"

Brilliant! Thank you so much!

Awesome explanation my man!

Good explanation. After understanding the logic I implemented the code myself. Feels good.

Thank you! Great video

Real cool explanation, Thanks Man.

a great explanation !. Thanks

OMG, man, you possess a special talent to explain complicated things smoothly and simple. I'm a big fan of your channel!

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.

Great practical explanation of Trie!!

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!

Loved the easy to understand explanation. 🧡 from remote.

When I did this one before wathcing the video, my code was double the length of yours. Nice solve!

What an amazing explanation for the guy who just started learning tries 👍

Brilliant explanation

You’re awesome dude ty

Amazing explanation

You are always the best!

This was one of the more enjoyable problems I've done

really helpful thank you so much.

please explain time and space complexity after u solve the problem

@juliacheng4751

2 жыл бұрын

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)

Great simple explanation

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

Nice explanation!

Great explanation

Neat video! Please do a video on Design Search Autocomplete System.

Excellent explanation

thanks! I thought Trie is gonna be super hard, nice explanation

Thanks!

crisp and clear

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

@TechOnScreen

2 жыл бұрын

dude he is in google !.. someone truly said. Time is mightier than fate..

@antonyndungu5514

2 жыл бұрын

@@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

@TechOnScreen

2 жыл бұрын

@@antonyndungu5514 yeah dude.. hope some day we will have our luck too 😂

@antonyndungu5514

2 жыл бұрын

@@TechOnScreen True, can't wait for that :-)

brilliant!

Using a hash map was genius. Once I saw that, I went and redid my code before looking at the rest of ur solution

The code is marvelously simple considering how useful of a data structure this can be.

Thanks Man!

The best Trie Explanation

neatly implemented

good job

great video!

yess!! tries are cool

Awesome!

Very helpful

helpful video

Can you code up the delete functionality as well ?

skimmed through 3-4 blah blah videos, this finished the job gracefully

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!

Thanks

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.

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.

Keep doing more videos

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'.

@mohammedfahadnyc1385

Жыл бұрын

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.

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?

@kamaleshs5324

2 жыл бұрын

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.

@DeGoya

2 жыл бұрын

@@kamaleshs5324 that doesn't answer the question though, since he asked what will happen if "we insert a substring of an already existing string"

@torin755

2 жыл бұрын

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

this guy is making our life play on easy mode

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

If you could have explained all the data structures like this before, My life would have become easier..

@qR7pK9sJ2t

5 ай бұрын

But did you come earlier to get his help is the question that I want to ask from you ?

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.

@hillarioushollywood4267

Жыл бұрын

not n nodes can have n children, you can say, 26 chars can have n children :) That Means, O(n+m+k+.........26th l)

@hamoodhabibi7026

Жыл бұрын

@@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

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?

@sirmidor

Жыл бұрын

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.

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

@atharhussain6534

Жыл бұрын

Data structure look like for letter apple : {"a":{"p":{"p":{"l":{"e:{}}}}}

you are the best

what's the complexity of search, insert, delete the word in the trie? when it's implemented using a 26 array? I'm tryna guess it? the search and insert is O(L which is the length of the word)? the all space is 26 * the number of all nodes? plz I need to know

Do we have to use trieNode? I used dictionary and had "None" to mark if the node is at the end.

This is the best Data Structure, I can think of 100s of things I can do with Trie. Well explained, I can say the speed at which you teach is on-target, I never fast-track your videos.

I like this one

Perfect