Just a small request, please do comment “understood” if you understand by watching this video. Helps me a lot mentally. Hardly will take 2 seconds!! Lets start this trend on TUF for every video you watch ☺️
Completed Trie Series, I can definitely say your way of teaching is best in the teaching field. Thanks for providing this type of highly rated content free of cost. 🙏
Understood!!! You explained so good that after watching the insert explaination of trie (till 13:23), I paused the video and coded insert, search and startsWith. After that I resumed video to match the code.
Small Correction at 24:57 in C++ code line 42, when we will move to the reference trie it should be node=node->get(word[i]); instead of just node->get(word[i]); By the way great content and really nice explanation :)
This video is really good. I was actually looking for a Trie playlist. I started trie a week back from gfg but couldn't understand. Now I'm starting again from your playlist. Please continue making videos for this playlist so that I can complete this concept timely. Thank you. Lots of support. And yeah, "understood".
I was always demotivated by the complexity in Tries.. For the very first time i understood everything.. I felt very high after being able to code it in python myself.... Thanks man ❤
Here is the python code for my fellow pythonistas:- class Node(): def __init__(self) -> None: self.links=[None for _ in range(26)] self.flag=False def containsKey(self,ch): return self.links[ord(ch)-ord('a')]!=None
class Trie(): def __init__(self): self.root=Node()
def insert(self,word): node=self.root for i in word: if(not node.containsKey(i)): node.put(i,Node()) node=node.get(i) node.setEnd() def search(self,word): node=self.root for i in word: if(not node.containsKey(i)): return False node=node.get(i)
return node.isEnd()
def startsWith(self,prefix): node=self.root for i in prefix: if(not node.containsKey(i)): return False node=node.get(i) return True if __name__=='__main__': type=[1,1,2,3,2] value=['hello','help','help','hel','hel'] trie=Trie() for i in range(len(type)): if(type[i]==1): trie.insert(value[i]) elif(type[i]==2): print(trie.search(value[i])) else: print(trie.startsWith(value[i]))
Just a small correction in C++ code line 42, when we will move to the reference trie it should be node=node->get(word[i]); instead of just node->get(word[i]); And 2nd one is line 13, return type is void instead of bool. Btw amazing video to understand trie in better way.
He was right when he said He'll not be running the code as he might have done some syntax errors, and he really has, at 24:57 in C++ code line 42, it will be node=node->get(word[i]); instead of just node->get(word[i]). Man is even ahead of himself.
Starting this trie series. Always wanted to study about tries because I am unable to solve hard questions requiring it's concepts. Hopefully I get clarity with this series. Completed tree series first before starting this!
I have a doubt in insertion part consider a word "app" if we first insert it then p will point to null and later if we insert "apple" now p is pointing towards 'l' so here we have lost the fact that "app" word also exists as by our word we should get a null node. So how to deal with this problem @take U forward @Striver
@akshay Actually, I was also thinking about the same problem The first time when "app" will be inserted, the second p will point to a null trie and that flag will be marked as true Later when "apple" is inserted then it would look like this ('a', false)->('p', false)->('p', false)->('l'-> *true*)->('e'->false)->(NULL->true) So after you search for "app", it will still return true
Fantastic explanation! Just two suggestions: 1. For Striver: Small letters t and f are looking identical in your writing, so consider writing T or F in capitals for added clarity. 2. For Viewers: This is a good way when you are guaranteed that the strings given are between a to z and in small case. If you have to generify it for all characters, how would you change it? Think about this question a little. :)
Hey striver I am able to understand trie concepts taught by you but I am having difficulty in understanding Object oriented stuff in C++ that you are telling in the video. Could you please recommend some resource from where we can learn this OOPS stuff conceptually or the resource from you learned and mastered it.
Can some explain me the time complexity of insertion- I have a doubt in insertion we are creating a pointer array of size 26 so why time complexity is o(n) it should be o(26*n)?
Nice and clear explanation! Just one question. Is there any specific reason for using a struct for Node instead of using a class like the way it has used in the Java code?
what if we have a word and its prefix as another word how are wo gonna handle that case as last char will not point to blank so we will conclude that this word is not present but is is present actually
Just a small request, please do comment “understood” if you understand by watching this video. Helps me a lot mentally. Hardly will take 2 seconds!!
Lets start this trend on TUF for every video you watch ☺️
IN thumbnail it should be implement TRIE instead of implement TREE
I completed the SDE sheet still imposter syndrome is killing me 😢, I'm at my 5th semester
bhaiya your explanation is the best.
understood
Thanks s'TRIE'ver for this amazing 'TRIE' playlist.. 😅😁📌
Completed Trie Series, I can definitely say your way of teaching is best in the teaching field. Thanks for providing this type of highly rated content free of cost. 🙏
Understood!!! You explained so good that after watching the insert explaination of trie (till 13:23), I paused the video and coded insert, search and startsWith. After that I resumed video to match the code.
At 29:30 ,in startsWith func(),for loop should be from i=0 to i
Yupo
Understood. No one can do a dry run like you do. You are perfect.
Small Correction at 24:57 in C++ code line 42, when we will move to the reference trie it should be node=node->get(word[i]); instead of just node->get(word[i]); By the way great content and really nice explanation :)
Yes.. current node is updating every times
Yes Exactly I was also wondering the same.
same I was thinking.
bro u have literally saved my day ,i was really confused how this was working
Not only did I understand, but also revised & learned best practices using OOPs.
This video is really good. I was actually looking for a Trie playlist. I started trie a week back from gfg but couldn't understand. Now I'm starting again from your playlist. Please continue making videos for this playlist so that I can complete this concept timely. Thank you. Lots of support. And yeah, "understood".
Thank you so much. I finally learnt Trie. After your explaination and seeing the struct Node. I decided to give it a try and code on my own. In
I was always demotivated by the complexity in Tries.. For the very first time i understood everything.. I felt very high after being able to code it in python myself.... Thanks man ❤
Understood. Also, I was able to solve the shortest unique prefix problem by only watching this video. Great explanation!!. Thanks a lot for this!
UNDERSTOOD........Thank You So Much for this wonderful video.............👍👍🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Here is the python code for my fellow pythonistas:-
class Node():
def __init__(self) -> None:
self.links=[None for _ in range(26)]
self.flag=False
def containsKey(self,ch):
return self.links[ord(ch)-ord('a')]!=None
def get(self,ch):
return self.links[ord(ch)-ord('a')]
def put(self,ch,node):
self.links[ord(ch)-ord('a')]=node
def setEnd(self):
self.flag=True
def isEnd(self):
return self.flag
class Trie():
def __init__(self):
self.root=Node()
def insert(self,word):
node=self.root
for i in word:
if(not node.containsKey(i)):
node.put(i,Node())
node=node.get(i)
node.setEnd()
def search(self,word):
node=self.root
for i in word:
if(not node.containsKey(i)):
return False
node=node.get(i)
return node.isEnd()
def startsWith(self,prefix):
node=self.root
for i in prefix:
if(not node.containsKey(i)):
return False
node=node.get(i)
return True
if __name__=='__main__':
type=[1,1,2,3,2]
value=['hello','help','help','hel','hel']
trie=Trie()
for i in range(len(type)):
if(type[i]==1):
trie.insert(value[i])
elif(type[i]==2):
print(trie.search(value[i]))
else:
print(trie.startsWith(value[i]))
Thanks man
Long lasting trie-phobia has been recovered. Thanks for the content.
love you dada from Howrah, West Bengal. You are my inspiration.... :)
Just a small correction in C++ code line 42, when we will move to the reference trie it should be node=node->get(word[i]); instead of just node->get(word[i]); And 2nd one is line 13, return type is void instead of bool. Btw amazing video to understand trie in better way.
i was also thinking the same
There is no error in line 13 , I mean return type would be bool only not void. I guess you meant in line 23, it should be void
Understood? Was able to code in a single attempt without looking anywhere else. That's how simple u made it 👍❤️
He was right when he said He'll not be running the code as he might have done some syntax errors, and he really has, at 24:57 in C++ code line 42, it will be node=node->get(word[i]); instead of just node->get(word[i]). Man is even ahead of himself.
Understood, bhaiya one thing that I want to request that please keep your face in every video while teaching. It would be great 🙂
Yes now it will be there
UNDERSTOOD Striver :) Thank you so much for all your efforts! Truly appreciable!
So far the best Trie Data Structure video on youtube
Understood bro. first video in life to understand trie and learned it in first video. What a luck for me
A FEEDBACK CODING LIVE IS MUCH MUCH BETTER THAN EXPLAINING THE WRITTEN SOLUTION..PLEASE FOLLOW THE SAME METHOD FOR FURTHER SERIES!!!1THANKS :)
Starting this trie series. Always wanted to study about tries because I am unable to solve hard questions requiring it's concepts. Hopefully I get clarity with this series. Completed tree series first before starting this!
understood sir ji
very nice video sir
your hardwork is amazing !!!
What happens when we try to insert a string that is a prefix of previously inserted string???
Its really so nice..Understood each and everything..
Understood! Thanks a lot for such a detailed and understandable tutorial!
Google is lucky to have you 😎😎😎
Understood! reallly a great explaination able to understand in one shot!
why the return type of setEnd() is bool, shouldn't it be void if it isn't returning anything
Thank you 😊
in search function, it should be prefix.length instead of word
I have a doubt in insertion part consider a word "app" if we first insert it then p will point to null and later if we insert "apple" now p is pointing towards 'l' so here we have lost the fact that "app" word also exists as by our word we should get a null node. So how to deal with this problem @take U forward @Striver
when we done traversing the word "app" we will check for the flag == true if yes then word exist otherwise not.
@akshay
Actually, I was also thinking about the same problem
The first time when "app" will be inserted, the second p will point to a null trie and that flag will be marked as true
Later when "apple" is inserted then it would look like this
('a', false)->('p', false)->('p', false)->('l'-> *true*)->('e'->false)->(NULL->true)
So after you search for "app", it will still return true
people would say that trie is a hard topic, but with you, it does not seem so
Understood! Really Appreciate it!
thanks a lot!
Keep making these type of content for us!
Thank you very much it is very much helpful.
node = node->get(word[i]) in insert method
Just woke up.
This video is go-with-my-breakfast video❤️
Just Awesome. Thanks a lot Striver.
Understood...btw striver you have a great teaching proficiency my friend...as amazing as it can be...🔥🔥✌
Striver hai toh Trie ko try krskte hai, only DS skipped will try to do now!, Great and lucid explanation ,cheers 🍻🍻
Awesome Explanation!
UNDERSTOOD TO THE FULLEST!
Understood excited for the upcoming videos thanq Striver🤩🤩
Understood in one go! Thanks for the concise explanation!
Leetcode daily challenge forced me to come here.. Happy I did!!!
Explaining complicated ds like a pro is jst a striver bhaiyya thing nobody else can do that💯
Understood !!!!!
Amazing explanation ,it was so easy
What is the prerequisite for Trie? also, before or after DP? @anyone and @everyone
understood! quick question though, can't we use a char to int map instead of the array?
Fantastic explanation! Just two suggestions:
1. For Striver: Small letters t and f are looking identical in your writing, so consider writing T or F in capitals for added clarity.
2. For Viewers: This is a good way when you are guaranteed that the strings given are between a to z and in small case. If you have to generify it for all characters, how would you change it? Think about this question a little.
:)
Sure Harsha, my handwriting is super bad 🤪
@@takeUforward Hey, no. Don't take it in a negative sense. Except for that one instance, your handwriting is pretty much fine.
@@takeUforward Btw, which Whiteboarding tool are you using?
Understood!!! , great explaination
Bhai kmal he krdea hitna difficult lgta tha ye topic Lekin abb bhot easy❤️
Hey striver I am able to understand trie concepts taught by you but I am having difficulty in understanding Object oriented stuff in C++ that you are telling in the video. Could you please recommend some resource from where we can learn this OOPS stuff conceptually or the resource from you learned and mastered it.
Such a great video! Easily understood and thanks for providing us with such contents.
Wall paper pe correct kar lo bhaiya Implement tree dikha raha hai !!
Awesome Explanation !!! And thanks for explaining the production level code .
compleately understood sir you are amazing
links could be taken as a map , It would reduce the complexity of containsKey class function a little bit.
I can not do anything for you but....Just thank you so much Bhaiya ❤️... Learnt a lot form you.... Inspiration to work hard 🙏
understood striver...you are a gem.
void insert(struct TrieNode *root, string key)
{
TrieNode *node = root;
for(int i=0;ichildren[key[i] - 'a']==NULL)
{
node->children[key[i] - 'a']= new TrieNode;
}
node=node->children[key[i] - 'a'];
}
node->isLeaf = true;
}
//Function to use TRIE data structure and search the given string.
bool search(struct TrieNode *root, string key)
{
TrieNode *node = root;
for(int i=0;ichildren[key[i] - 'a']==NULL)
{
return false;
}
node = node->children[key[i] - 'a'];
}
return node->isLeaf;
}
UnderStood
You said production level code , So
Can we use range based for loops whenever index is not required ?
Thanks a lot for this valuable things a for free.
That was cool... got the concept and implementation pretty clearly.. All thanks to you bro.
Understood !!! sure man thank you so much for sharing keep pushing that content
Why can't we directly use Trie class to represent Nodes? What is the benefit of using different class to represent Trie Nodes?
hey! akash striver ne directly questions karwayein h ya phele trie ke baare mei btaya bhi h
Understood.
Which notepad are you using for writing ?
amazing lecture sir😍
thank you so much 🙏🙏
Great Explanation! Understood very well.
Default Value of all element of array is pointer is NULL ??
teaches well understood well😊
Great content as always. Btw How to insert "apples" AFTER inserting "apple". Wouldn't "apple" be lost?
No e’s reference trie has true marked, so u add a new trie for s to e’s reference trie and for s’s reference trie mark it as true
Can some explain me the time complexity of insertion-
I have a doubt in insertion we are creating a pointer array of size 26 so why time complexity is o(n) it should be o(26*n)?
Understood. Hats Of!!!!!!!!!!!!!!1
Understood... super explanation...
Understood striver Thank you
Nice and clear explanation! Just one question. Is there any specific reason for using a struct for Node instead of using a class like the way it has used in the Java code?
Great explanation and coding with industry standards. This will help not only in the interview but also in the daily work.
if 'ba" exists then why not 'appl"? in that case after "l" we will be at not null position as well.
Understood bhaiya. Keep making this type of amzing content :)
For all those complaining for the background
Striver also noticed that hence placed his photo just over that e
Brilliant
Please make a video of suffix array which jnvloves nlogn solution
Thnks
Understood ! Very well explained !!
Awesome Explanation! 🔥
UNDERSTOOD
Very Well understood. Thanks bhayya
Main tera haaye re jabra
Hoye re jabra fan ho gaya!
Why do we need an extra struct can't we do it using a class Only?
You are the best, man!
Understood, very nice lecture 😉
Time traveller 😳
Can u tell the space complexity of trie , because we are taking the links array again and again for reference trie??
Striver bhai, you're the best!
understood !!!
Understood. Thanks, Raj!
Watched it completly Raj Sir
bro, you are doing great work, learnt a lot from your videos....thanks for providing such a quality content.
One doubt: How to insert "apps" and "app" in a trie ?? or "apples" and "apple" ??, please reply
Understood. Really helpful.
understood Striver. Thank you.
best teacher ever
what if we have a word and its prefix as another word how are wo gonna handle that case as last char will not point to blank so we will conclude that this word is not present but is is present actually