Wow, I'm watching this on Sat morning as a warmup exercise to my coding routines. Amazing in its simplicity, coherence and how the author went straight to the point.
Thanks, very clear explanation. "isWord" flag is fucking awesome, you can hold two words in the same path like cat and cats. With this flag when we search "cat", it will return it as true.
Very good content. Just for the sake of contribution, I found out that the property 'c' in your node is actually not needed. You can surpress it without losing information in your structure. This information is already there in the children array of nodes.
Nice, just 2 questions, do you really need that array of [26], i mean it seems like a waste of resource, b'c the Node itself as has 'c', so a ten letter word would have 10 nodes, no need to utilize an array[26]. Lastly, why not utilizes recursion at some point. Thanks, I am bit out of touch with tree structures and recursion, not since college have to implemented them, so would appreciate a broad answer, thanks.
For the most part I get the video, but I can't seem to figure out why in the return statement in 'search(String word)' has to include 'node != null.' I got rid of it and it passed the 'Run Code' test but not the submission itself E: nvm. it's because 'curr' can point to a null spot in the array in the case that a prefix is not found in the trie. 'null' doesn't have any methods, but it doesn't give you an error because of short-circuiting. it sees null IS null and just spits out 'false' without checking 'null.isWord()'
Instead of having an array of length 26 defined for each node, you could just use a set for each node and add it’s children using a character -> node key value pair
Anyone able to provide some input on what (if any) the performance difference would be between creating looping over char c : word.toCharArray() versus looping over the string via an index variable and extracting the char at each iteration with char c = word.charAt()?
One issue I noticed there is in case someone passes an ASCII entry above 'z', program is going to attempt to access an invalid index into its array. Either checking or making it wrap around with remainder of division by 26 is required to prevent that.
Hey Michael, i really liked your explanation, but i have a question regarding using array and intializing its length, does this affect space complexity since we take 26 spaces in memory every time we insert one character ? thats why using a hashmap is more efficient, though i really prefer this solution because its cleaner and easier to understand, thanks again
I have a question! I'm getting a index out of bounds error at line 36, if(curr.children[c - 'a'] == null) return null; Can someone explain why it might've happened?
@@AlgosWithMichael I've double-checked and it is a lowercase letter. Not too sure what's wrong with it! Also, thank you for the great explanation in the video! :)
Fantastic video! thank you so much! You really are an amazing teacher. my only question though is why did you need a char member variable in your Node class. I wrote mine and noticed the data structure operates perfectly fine without that "char" member variable in the Node class.
Hey Michael, i got a question. At line 15-16 (In insert method) i don't understand what happens if curr.children[c-'a'] is not equal to null. If we are inserting Strings, for example ,st1= "Apple" and st2 = "Add" how can A point to P and D at the same time. When we are inserting "ÄDD" Since curr.children[a-'a'] != null. It moves to Node with value P. A new node for D is not created. Thanks.
The way characters point to other characters is each node has a `children` array of nodes representing all possible characters in the alphabet. If the index at `c - 'a'` evaluates to null, that means a new node needs to be created at that index. Hope that helps!
Optimization of space requirements: It seems that we don't need the instance variable 'char c'. And the boolean variable 'isWord' could be avoided if we have 2 classes: 'Node' with method 'isWord()' returning false, and a subclass 'EndNode' which overrides 'isWord' now returning true. Instead of setting the variable value, we replace the object (once).
I got a question in like if we want to print the vertices by numbering the edges in order of insert ....how can we do this... for example 1 : input - 1 ABC output - 0 -> 1 A 1 ->2 B 2 ->3 C for example 2: input 3 AT AG AC output - 0 -> 1 A 1 -> 4 C 1 -> 3 G 1 -> 2 T THANKS FOR HELPING.....
It is because 'a' in ascii is 97 in its decimal value. Any lowercase letter minus 'a' will give you the index of the letter. So as an example, say I want to get the index of 'b'. 'b' has a decimal value of 98 (1 more than 'a'). So we subtract 'b' - 'a' and that gives us 1 as the index. 0 is index 'a', 1 is index 'b', etc. Hope this makes sense!
Why your search is O(1) if you have a search function with an iteration through N letters, think you are doing a linear search, so i think your search it's O(N), any thing im missing?
//Search Insert and Delete are discussing Below public class Implementation{ static class Node{ public char c;//We are dealing with only small values; public boolean isWord; public Node[] childern;//Store all the childerns in this Node. Node(char c){ this.c = c; isWord = false; childern = new Node[26]; } } static class Trie{ private Node root; public Trie(){ root = new Node('\0'); } public void insert(String word){ Node curr = root; for(int i=0;i
Just came across this ... good work and nice graphical instruction. I do have a concern over the "StartsWith(prefix)" method as it does not work as I would expect. In your implementation, If you have the word 'cat' in the trie but not any other word beyond that, like 'cats' or 'catastrophe' your StartsWith('cat') would return true even though you have no more words beyond that point. Therefore, a subsequent Search('cats') or any Search/StartsWith('cat' + any character(s)) would return false. I would expect the StartsWith to check to be sure there are nodes in the children array to indicate a longer word is available in your trie. Example: 'cat', 'cats', and 'catastrophe' were inserted to the Trie and performing a StartsWith('cat') would return true because there are more nodes below 't' Example 2: 'cat' was inserted to the Trie and performing a StartsWith('cat') would return FALSE because there are no children nodes below 't' What are your thoughts?
Great and very simplified... But small correction in insert method public void insert(String word) { Node current = root; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); if (current.children[c - 'a'] == null) { current.children[c - 'a'] = new TrieNode(c); current = current.children[ch - 'a']; }else if(current.children[ch - 'a'].c == c){ current = current.children[c - 'a']; } } current.isWord = true; }
Why is Node a class instead of a struct? You will have many nodes and a class requires more memory than a struct. You are also using "c - 'a' " in a loop. Put that into a variable and do the calculation once. Why pay for the calculation over and over. You didn't use the term ASCII, which is surprising, as it may help viewers to understand that this is the case. Why not make this recursive, rather than using so many for loops. At the end a trie is just a modification of a binary tree, but it can have 26 children. Nice video though.
Yea, I could have put c - 'a' in a variable. I think using loops is easier to understand than recursive approaches, especially if I am trying to explain a concept that people don't know already. Thanks for the feedback!
@@AlgosWithMichael Thanks for the reply. If you just mentioned that there are other options that would be enough. My concern is people will look at your video, then just copy it and not realize that it not the best choice, as this was written to teach, not for production. This happens when people put snippets of code on StackOverflow also.
This is gold. 👏👏👏 Couldn’t find a better explanation of Trie. Thanks brother
No problem 👍
Thanks Michel, the video was so good that I could write a Trie DS myself within 20 mins.
Good one! Small optimization/correction - char c at each Node can be removed (not needed).
@John Gelson you don't. Isn't the location (index) in (Node[]) array represent the letter (ASCII value) itself?
checking for Trie implementation all over the internet finally found and he also explained very well thanks, bro....
What an amazing explanation! By far the best. He makes difficult concepts look so easy and very intuitive.
Thank you so much, Michael.
You're very welcome!
Man, whenever I see your face after a google search on a data structure I feel a sense of relief. Thanks a lot for making these amazing videos.
That is such a huge compliment, thank you so much!
I've always find your videos are useful...Great Explanation....This channel deserves more subscribers..
I appreciate that, I try to put a lot of effort in my videos!
Wow, I'm watching this on Sat morning as a warmup exercise to my coding routines. Amazing in its simplicity, coherence and how the author went straight to the point.
Best video on Tries on TH-cam - Thank you so much. I just subscribed myself.
Best description on tries ever! I've watched other ones but they were more complicated for some reason
Thank you!
How I didn’t discover you sooner, your explanation is the best!
Great explanation. No more time than it needs to take to explain the DS. Awesome work dude. Keep it up.
Much appreciated!
Good job brother, you are really crisp and articulate with your thought process and approach towards explaining things. Wish you success , cheers 🥂
Thanks, very clear explanation. "isWord" flag is fucking awesome, you can hold two words in the same path like cat and cats. With this flag when we search "cat", it will return it as true.
Very calm, easy and straight forward explanation.. thanks
Very good explanation, thank you!
this is incredible, fantastic work Michael
Thank you!
Really great explanation. Now I feel confident that if I get a question on trie I can easily implement it.
Awesome!
Thanks for being such an awesome source
My pleasure!
This guy never disappoints...
Hahaha I appreciate that, thanks for watching!
Seriously never ❤️
Haha thank you!
Great explanation. Simple and plain.
Thank you Michael. You made this easy to understand. Thank you.
Awesomeeeee! Thank you so much Michael
No problem
Congrats bro!! You've actually made me understand smthg!
Haha awesome!
very useful approach
dude ur a fucking great teacher, do you know that? love you brother!
Great video!
If we wanted to add a delete method, would we just getNode and then set isWord to false?
earned yourself a subscriber. legit video
Thanks Ben!
very helpful, thanks Michael!
You are doing a great job. You are maintaining the quality of the contents. Could you add some detailed videos on tries?
Yea, I can definitely do more Trie videos. Thanks for watching!
it was nice ; thanks Michael !
many many thanks bro! amazing explanation and easy to comprehend.
Very good content. Just for the sake of contribution, I found out that the property 'c' in your node is actually not needed. You can surpress it without losing information in your structure. This information is already there in the children array of nodes.
Ah good point, thanks for that!
Nice, just 2 questions, do you really need that array of [26], i mean it seems like a waste of resource, b'c the Node itself as has 'c', so a ten letter word would have 10 nodes, no need to utilize an array[26]. Lastly, why not utilizes recursion at some point. Thanks, I am bit out of touch with tree structures and recursion, not since college have to implemented them, so would appreciate a broad answer, thanks.
👏Great explanation and great coding!! Thanks.
Great explanation!
Glad it was helpful!
For the most part I get the video, but I can't seem to figure out why in the return statement in 'search(String word)' has to include 'node != null.' I got rid of it and it passed the 'Run Code' test but not the submission itself
E: nvm. it's because 'curr' can point to a null spot in the array in the case that a prefix is not found in the trie. 'null' doesn't have any methods, but it doesn't give you an error because of short-circuiting. it sees null IS null and just spits out 'false' without checking 'null.isWord()'
it's a great video! Very clear explanation. I was just curious why you used an array for children Nodes instead of a map? Is it just your preference?
Hi! Thanks so much for this video. Could you please tell us what kind of keyboard you use lol
Thank you bro for this video.
Is there any specific reason to have Node as inner class??
Subscribed you!! thanks for the great explanation.
thanks for this super useful video.
Thanks for this great video :)
You have a new subscriber :)
Welcome aboard!
This is amazing, thank you!
No problem 😊
Hi could you help me about Multi-index Hybrid Trie for IP Lookup and Updates?
Thanks Bro! You made my day 🤘
Glad I could help!
This was very helpful. Thank you.
Of course!
Which software are you using for explanation?
Instead of having an array of length 26 defined for each node, you could just use a set for each node and add it’s children using a character -> node key value pair
Yep you can do that as well 👍
Anyone able to provide some input on what (if any) the performance difference would be between creating looping over char c : word.toCharArray() versus looping over the string via an index variable and extracting the char at each iteration with char c = word.charAt()?
One issue I noticed there is in case someone passes an ASCII entry above 'z', program is going to attempt to access an invalid index into its array. Either checking or making it wrap around with remainder of division by 26 is required to prevent that.
true, but this specific problem states that we can assume that all chars will be between a-z
This is neat! Can you please do a video on Design Search Autocomplete System
Hey Michael, i really liked your explanation, but i have a question regarding using array and intializing its length, does this affect space complexity since we take 26 spaces in memory every time we insert one character ? thats why using a hashmap is more efficient, though i really prefer this solution because its cleaner and easier to understand, thanks again
Thanks a lot! This was really helpful!
Glad it helped!
I have a question! I'm getting a index out of bounds error at line 36, if(curr.children[c - 'a'] == null) return null;
Can someone explain why it might've happened?
Is it possible your character 'c' is not a lowercase letter?
@@AlgosWithMichael I've double-checked and it is a lowercase letter. Not too sure what's wrong with it! Also, thank you for the great explanation in the video! :)
Fantastic video! thank you so much! You really are an amazing teacher. my only question though is why did you need a char member variable in your Node class. I wrote mine and noticed the data structure operates perfectly fine without that "char" member variable in the Node class.
Amazing fact
Hey Michael, i got a question. At line 15-16 (In insert method) i don't understand what happens if curr.children[c-'a'] is not equal to null. If we are inserting Strings, for example ,st1= "Apple" and st2 = "Add" how can A point to P and D at the same time. When we are inserting "ÄDD" Since curr.children[a-'a'] != null. It moves to Node with value P. A new node for D is not created.
Thanks.
The way characters point to other characters is each node has a `children` array of nodes representing all possible characters in the alphabet. If the index at `c - 'a'` evaluates to null, that means a new node needs to be created at that index. Hope that helps!
nice one mike good vid.
Thanks dude!
Amazing video!!!
Thank you!
Optimization of space requirements:
It seems that we don't need the instance variable 'char c'. And the boolean variable 'isWord' could be avoided if we have 2 classes: 'Node' with method 'isWord()' returning false, and a subclass 'EndNode' which overrides 'isWord' now returning true. Instead of setting the variable value, we replace the object (once).
I got a question in like if we want to print the vertices by numbering the edges in order of insert ....how can we do this...
for example 1 : input -
1
ABC
output -
0 -> 1 A
1 ->2 B
2 ->3 C
for example 2: input
3
AT
AG
AC
output -
0 -> 1 A
1 -> 4 C
1 -> 3 G
1 -> 2 T
THANKS FOR HELPING.....
Hmmm tough question
Could someone maybe explain again why 'a' is subtracted from the char? Just a little confused there...
It is because 'a' in ascii is 97 in its decimal value. Any lowercase letter minus 'a' will give you the index of the letter. So as an example, say I want to get the index of 'b'. 'b' has a decimal value of 98 (1 more than 'a'). So we subtract 'b' - 'a' and that gives us 1 as the index. 0 is index 'a', 1 is index 'b', etc.
Hope this makes sense!
@@AlgosWithMichael thanks that helps a lot 😊
Great Video
Thanks!
Why your search is O(1) if you have a search function with an iteration through N letters,
think you are doing a linear search, so i think your search it's O(N), any thing im missing?
Space complexity is O(1), time complexity is O(N)
@@AlgosWithMichael Got it, ty
Awesome. thanks!
Of course!
Which language is this?
Thanks mate
Anytime :)
//Search Insert and Delete are discussing Below
public class Implementation{
static class Node{
public char c;//We are dealing with only small values;
public boolean isWord;
public Node[] childern;//Store all the childerns in this Node.
Node(char c){
this.c = c;
isWord = false;
childern = new Node[26];
}
}
static class Trie{
private Node root;
public Trie(){
root = new Node('\0');
}
public void insert(String word){
Node curr = root;
for(int i=0;i
Thank you so much!
No worries!
Amazing
LMAO, The kids yeeeaaah voice 🤣🤣🤣
from where i get he full code?
I don't have it posted anywhere :/
Just came across this ... good work and nice graphical instruction.
I do have a concern over the "StartsWith(prefix)" method as it does not work as I would expect.
In your implementation, If you have the word 'cat' in the trie but not any other word beyond that, like 'cats' or 'catastrophe' your StartsWith('cat') would return true even though you have no more words beyond that point. Therefore, a subsequent Search('cats') or any Search/StartsWith('cat' + any character(s)) would return false.
I would expect the StartsWith to check to be sure there are nodes in the children array to indicate a longer word is available in your trie.
Example: 'cat', 'cats', and 'catastrophe' were inserted to the Trie and performing a StartsWith('cat') would return true because there are more nodes below 't'
Example 2: 'cat' was inserted to the Trie and performing a StartsWith('cat') would return FALSE because there are no children nodes below 't'
What are your thoughts?
Great video! For the purposes of this question though, the information about the exact character inside a node is not needed.
True, thank you so much for watching!
Ah, since the children have an array of the alphabet anyways, the actual c element of the Node class is not needed. Just FYI. Thanks!
Yea, that is a good point! Thanks for watching
Great and very simplified...
But small correction in insert method
public void insert(String word) {
Node current = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (current.children[c - 'a'] == null) {
current.children[c - 'a'] = new TrieNode(c);
current = current.children[ch - 'a'];
}else if(current.children[ch - 'a'].c == c){
current = current.children[c - 'a'];
}
}
current.isWord = true;
}
Why is Node a class instead of a struct? You will have many nodes and a class requires more memory than a struct. You are also using "c - 'a' " in a loop. Put that into a variable and do the calculation once. Why pay for the calculation over and over. You didn't use the term ASCII, which is surprising, as it may help viewers to understand that this is the case. Why not make this recursive, rather than using so many for loops. At the end a trie is just a modification of a binary tree, but it can have 26 children. Nice video though.
Yea, I could have put c - 'a' in a variable. I think using loops is easier to understand than recursive approaches, especially if I am trying to explain a concept that people don't know already. Thanks for the feedback!
@@AlgosWithMichael Thanks for the reply. If you just mentioned that there are other options that would be enough. My concern is people will look at your video, then just copy it and not realize that it not the best choice, as this was written to teach, not for production. This happens when people put snippets of code on StackOverflow also.
شايفكم ي عيال كفوبم وانتم تفشخون الحل هههه