L1. Implement TRIE | INSERT | SEARCH | STARTSWITH
Вставка
- Опубліковано 10 лис 2021
- Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- C++/Java Codes - takeuforward.org/data-structu...
Pre-requisite: Should know the concept of pointers, struct in CPP, classes in java, basic programming
In this video, we discuss the Insert, search and start with the functionality of TRIE Data Structure and its usage!
Please share this channel as much as you can. Also, it's an earnest request to drop a comment "understood" if you are watching this video, so that I get to know you understood from this video.
SDE-Sheet/Linkedin/Telegram/Instagram: linktr.ee/takeUforward
-------------------------------------------------------------------------------------------------------------
Problem Link: bit.ly/3n4m3Hu
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.
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
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
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 ❤
Understood. No one can do a dry run like you do. You are perfect.
At 29:30 ,in startsWith func(),for loop should be from i=0 to i
Yupo
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, 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
Not only did I understand, but also revised & learned best practices using OOPs.
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
Understood...btw striver you have a great teaching proficiency my friend...as amazing as it can be...🔥🔥✌
Long lasting trie-phobia has been recovered. Thanks for the content.
Understood in one go! Thanks for the concise explanation!
Such a great video! Easily understood and thanks for providing us with such contents.
Understood? Was able to code in a single attempt without looking anywhere else. That's how simple u made it 👍❤️
Understood! Really Appreciate it!
thanks a lot!
Keep making these type of content for us!
Thank you very much it is very much helpful.
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
That was cool... got the concept and implementation pretty clearly.. All thanks to you bro.
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
Awesome Explanation !!! And thanks for explaining the production level code .
love you dada from Howrah, West Bengal. You are my inspiration.... :)
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! Thanks a lot for such a detailed and understandable tutorial!
Understood bro. first video in life to understand trie and learned it in first video. What a luck for me
Awesome Explanation!
UNDERSTOOD TO THE FULLEST!
Understood !!!!!
Amazing explanation ,it was so easy
So far the best Trie Data Structure video on youtube
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 Striver :) Thank you so much for all your efforts! Truly appreciable!
Understood! reallly a great explaination able to understand in one shot!
Striver hai toh Trie ko try krskte hai, only DS skipped will try to do now!, Great and lucid explanation ,cheers 🍻🍻
amazing lecture sir😍
thank you so much 🙏🙏
Great explanation and coding with industry standards. This will help not only in the interview but also in the daily work.
Explaining complicated ds like a pro is jst a striver bhaiyya thing nobody else can do that💯
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.
Its really so nice..Understood each and everything..
bro, you are doing great work, learnt a lot from your videos....thanks for providing such a quality content.
Great Explanation! Understood very well.
understood! quick question though, can't we use a char to int map instead of the array?
UNDERSTOOD........Thank You So Much for this wonderful video.............👍👍🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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 ! Very well explained !!
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?
Just woke up.
This video is go-with-my-breakfast video❤️
Wall paper pe correct kar lo bhaiya Implement tree dikha raha hai !!
Understood !!! sure man thank you so much for sharing keep pushing that content
A FEEDBACK CODING LIVE IS MUCH MUCH BETTER THAN EXPLAINING THE WRITTEN SOLUTION..PLEASE FOLLOW THE SAME METHOD FOR FURTHER SERIES!!!1THANKS :)
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
Awesome Explanation! 🔥
UNDERSTOOD
I can not do anything for you but....Just thank you so much Bhaiya ❤️... Learnt a lot form you.... Inspiration to work hard 🙏
Amazing explanation!!!!
What happens when we try to insert a string that is a prefix of previously inserted string???
Google is lucky to have you 😎😎😎
Bhai kmal he krdea hitna difficult lgta tha ye topic Lekin abb bhot easy❤️
understood striver...you are a gem.
Understood excited for the upcoming videos thanq Striver🤩🤩
why the return type of setEnd() is bool, shouldn't it be void if it isn't returning anything
understood , you are doing great job buddy
U r man of words respect 💯
Very Well understood. Thanks bhayya
Just Awesome. Thanks a lot Striver.
Perfectly understood!!
Understood bhaiya. Keep making this type of amzing content :)
Understood Completely!!!👍
UnderStood
You said production level code , So
Can we use range based for loops whenever index is not required ?
Understood. Hats Of!!!!!!!!!!!!!!1
understood :))) ! amazing work
What is the prerequisite for Trie? also, before or after DP? @anyone and @everyone
Understood. Really helpful.
Thanks a lot for this valuable things a for free.
Understood😎👍
Thanks a alot broo
UNDERSTOOD very well !
Understood... super explanation...
FULLY UNDERSTOOD 🏵🏵
people would say that trie is a hard topic, but with you, it does not seem so
compleately understood sir you are amazing
teaches well understood well😊
Leetcode daily challenge forced me to come here.. Happy I did!!!
You are the best, man!
Can u tell the space complexity of trie , because we are taking the links array again and again for reference trie??
links could be taken as a map , It would reduce the complexity of containsKey class function a little bit.
Brilliant
Please make a video of suffix array which jnvloves nlogn solution
Thnks
For all those complaining for the background
Striver also noticed that hence placed his photo just over that e
Understood!!! Too good
Understood. Great Content.
node = node->get(word[i]) in insert method
Understood, very nice lecture 😉
Time traveller 😳
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
Main tera haaye re jabra
Hoye re jabra fan ho gaya!
in search function, it should be prefix.length instead of word
UNDERSTOOOOOOOOOOOOOOOD !!!
Explanation OP !!!
Watched it completly Raj Sir
Striver bhai, you're the best!
Understood , awesome.
best teacher ever
Helpful video 😃