L1. Implement TRIE | INSERT | SEARCH

L1. Implement TRIE | INSERT | SEARCH | STARTSWITH

Рет қаралды 283,736

2 жыл бұрын

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

Пікірлер: 385

@takeUforward 2 жыл бұрын

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 ☺️

@agrawalhimanshu 2 жыл бұрын

IN thumbnail it should be implement TRIE instead of implement TREE

@hareeshr3979 2 жыл бұрын

I completed the SDE sheet still imposter syndrome is killing me 😢, I'm at my 5th semester

@noobprogrammer3040 2 жыл бұрын

bhaiya your explanation is the best.

@swapnilsingh710 2 жыл бұрын

understood

@aeroabrar_31 Жыл бұрын

Thanks s'TRIE'ver for this amazing 'TRIE' playlist.. 😅😁📌

@vikrambabariya5166 Жыл бұрын

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

@shree_divyansh 2 жыл бұрын

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.

@lakshyaKumar12 Жыл бұрын

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

@Ishan301 2 жыл бұрын

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 :)

@sukritiguin5637 2 жыл бұрын

Yes.. current node is updating every times

@ashutoshpatel5030 Жыл бұрын

Yes Exactly I was also wondering the same.

@rohitk472 Жыл бұрын

same I was thinking.

@K.AnshulReddy Ай бұрын

bro u have literally saved my day ,i was really confused how this was working

@tanujajoshi5253 2 жыл бұрын

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

@dharani8871 Жыл бұрын

Understood. No one can do a dry run like you do. You are perfect.

@likhithl7928 Жыл бұрын

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 ❤

@evergreen7781 2 жыл бұрын

Not only did I understand, but also revised & learned best practices using OOPs.

@bharathjanakiraman7232 2 жыл бұрын

Understood. Also, I was able to solve the shortest unique prefix problem by only watching this video. Great explanation!!. Thanks a lot for this!

@abhimanyubahree1455 7 ай бұрын

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

@prateekgaur2709 2 жыл бұрын

At 29:30 ,in startsWith func(),for loop should be from i=0 to i

@valobhediya Жыл бұрын

Yupo

@mohaimenchowdhury Жыл бұрын

Long lasting trie-phobia has been recovered. Thanks for the content.

@mohaktrivedi9591 2 жыл бұрын

Understood in one go! Thanks for the concise explanation!

@accessdeniedk6240 2 жыл бұрын

Such a great video! Easily understood and thanks for providing us with such contents.

@TheElevatedGuy 2 жыл бұрын

Understood! Really Appreciate it! thanks a lot! Keep making these type of content for us! Thank you very much it is very much helpful.

@utkarshmishra6667 2 жыл бұрын

Understood...btw striver you have a great teaching proficiency my friend...as amazing as it can be...🔥🔥✌

@akshatsahu8021 2 жыл бұрын

That was cool... got the concept and implementation pretty clearly.. All thanks to you bro.

@mohammedanasdanish7509 Жыл бұрын

Understood! Thanks a lot for such a detailed and understandable tutorial!

@AliAkbarFaiz 2 жыл бұрын

Understood? Was able to code in a single attempt without looking anywhere else. That's how simple u made it 👍❤️

@_SOHAMSAMANTA 2 жыл бұрын

Awesome Explanation !!! And thanks for explaining the production level code .

@bhushankorg5606 Жыл бұрын

Understood! reallly a great explaination able to understand in one shot!

@lakshaysharma6550 2 жыл бұрын

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]))

@av21015 Жыл бұрын

Thanks man

@AB-tp9eg 2 жыл бұрын

Understood, bhaiya one thing that I want to request that please keep your face in every video while teaching. It would be great 🙂

@takeUforward 2 жыл бұрын

Yes now it will be there

@aryanmaniyar7301 9 ай бұрын

UNDERSTOOD Striver :) Thank you so much for all your efforts! Truly appreciable!

@s.g.prajapati3597 2 жыл бұрын

Awesome Explanation! UNDERSTOOD TO THE FULLEST!

@yuvi3398 2 жыл бұрын

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.

@yashsinha4712 2 жыл бұрын

Understood !!!!! Amazing explanation ,it was so easy

@arnabmondal81 10 ай бұрын

love you dada from Howrah, West Bengal. You are my inspiration.... :)

@aditidey9366 2 жыл бұрын

understood! quick question though, can't we use a char to int map instead of the array?

@NinaadMallapur Жыл бұрын

So far the best Trie Data Structure video on youtube

@AhmadSayeed-plus 9 ай бұрын

Understood bro. first video in life to understand trie and learned it in first video. What a luck for me

@Dontpushyour_luck 9 ай бұрын

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!

@madhavaprashath1453 2 жыл бұрын

What happens when we try to insert a string that is a prefix of previously inserted string???

@sommayghosh4617 2 жыл бұрын

Striver hai toh Trie ko try krskte hai, only DS skipped will try to do now!, Great and lucid explanation ,cheers 🍻🍻

@ddwatcher Жыл бұрын

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?

@juliechoudhary9582 Жыл бұрын

Its really so nice..Understood each and everything..

@masterroyjones4228 2 жыл бұрын

Explaining complicated ds like a pro is jst a striver bhaiyya thing nobody else can do that💯

@itsyadavraj 2 жыл бұрын

amazing lecture sir😍 thank you so much 🙏🙏

@Manojkumar-rq8hf 2 жыл бұрын

Great Explanation! Understood very well.

@mallikdasari 2 жыл бұрын

Great explanation and coding with industry standards. This will help not only in the interview but also in the daily work.

@sks7856 2 жыл бұрын

bro, you are doing great work, learnt a lot from your videos....thanks for providing such a quality content.

@keshav2113 2 жыл бұрын

Wall paper pe correct kar lo bhaiya Implement tree dikha raha hai !!

@krishnamsinha8320 2 ай бұрын

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.

@stith_pragya 6 ай бұрын

UNDERSTOOD........Thank You So Much for this wonderful video.............👍👍🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

@sunnykumarsingh7039 2 жыл бұрын

Just woke up. This video is go-with-my-breakfast video❤️

@AbhishekSingh-oz5ei 10 ай бұрын

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.

@ankit462 10 ай бұрын

i was also thinking the same

@hardikkumarsingh 7 ай бұрын

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

@SriHarshaChilakapati 2 жыл бұрын

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. :)

@takeUforward 2 жыл бұрын

Sure Harsha, my handwriting is super bad 🤪

@SriHarshaChilakapati 2 жыл бұрын

@@takeUforward Hey, no. Don't take it in a negative sense. Except for that one instance, your handwriting is pretty much fine.

@SriHarshaChilakapati 2 жыл бұрын

@@takeUforward Btw, which Whiteboarding tool are you using?

@cenacr007 Жыл бұрын

why the return type of setEnd() is bool, shouldn't it be void if it isn't returning anything

@eshandhok2591 2 жыл бұрын

What is the prerequisite for Trie? also, before or after DP? @anyone and @everyone

@TechieDishant 2 жыл бұрын

Awesome Explanation! 🔥 UNDERSTOOD

@nbavideos4487 2 жыл бұрын

Understood !!! sure man thank you so much for sharing keep pushing that content

@akshaywairagade5478 2 жыл бұрын

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

@utkarshsharma1185 Жыл бұрын

when we done traversing the word "app" we will check for the flag == true if yes then word exist otherwise not.

@adarshgupta2605 Жыл бұрын

@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

@champion5946 2 жыл бұрын

UnderStood You said production level code , So Can we use range based for loops whenever index is not required ?

@bhaveshkumar6842 2 жыл бұрын

Google is lucky to have you 😎😎😎

@vibhaalur4078 2 жыл бұрын

Understood ! Very well explained !!

@siddharthsaxena6495 2 жыл бұрын

Can u tell the space complexity of trie , because we are taking the links array again and again for reference trie??

@parambharti7095 Жыл бұрын

Just Awesome. Thanks a lot Striver.

@areebahmadsiddiqui2648 2 жыл бұрын

Understood excited for the upcoming videos thanq Striver🤩🤩

@manishsah7755 6 ай бұрын

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)?

@therealsumitshah 2 жыл бұрын

understood striver...you are a gem.

@BEEMohdArbazAli 2 жыл бұрын

Very Well understood. Thanks bhayya

@atharvakulkarni2024 2 жыл бұрын

A FEEDBACK CODING LIVE IS MUCH MUCH BETTER THAN EXPLAINING THE WRITTEN SOLUTION..PLEASE FOLLOW THE SAME METHOD FOR FURTHER SERIES!!!1THANKS :)

@Niranjan-dt2mc 2 жыл бұрын

I can not do anything for you but....Just thank you so much Bhaiya ❤️... Learnt a lot form you.... Inspiration to work hard 🙏

@user-sl3vy8rm2r Жыл бұрын

people would say that trie is a hard topic, but with you, it does not seem so

@zahidgul6337 5 ай бұрын

in search function, it should be prefix.length instead of word

@atulk9122 2 жыл бұрын

U r man of words respect 💯

@atharvakulkarni2024 2 жыл бұрын

Why do we need an extra struct can't we do it using a class Only?

@bracb2278 Жыл бұрын

What if we search for the word "appse" ? As 's' is pointing to another flag true node, so it will not go on 'e' na?

@mohdaman7228 Жыл бұрын

links could be taken as a map , It would reduce the complexity of containsKey class function a little bit.

@rujwideshmukh5382 2 жыл бұрын

Amazing explanation!!!!

@devendrapatil07 2 жыл бұрын

Default Value of all element of array is pointer is NULL ??

@rishabhkumar8115 2 жыл бұрын

Thanks a lot for this valuable things a for free.

@subhadipmaity3253 Жыл бұрын

One doubt: How to insert "apps" and "app" in a trie ?? or "apples" and "apple" ??, please reply

@KnowledgeGuide859 6 ай бұрын

Understood. Which notepad are you using for writing ?

@akhilkishore7361 2 жыл бұрын

understood , you are doing great job buddy

@MayurNagrale-py7lu Жыл бұрын

node = node->get(word[i]) in insert method

@rohitantil9534 2 жыл бұрын

Bhai kmal he krdea hitna difficult lgta tha ye topic Lekin abb bhot easy❤️

@jaykumargupta7307 2 жыл бұрын

Leetcode daily challenge forced me to come here.. Happy I did!!!

@sachinaspiran Жыл бұрын

compleately understood sir you are amazing

@user-bw7gb1yr1p 10 ай бұрын

Understood... super explanation...

@Wtk_Ncs 2 ай бұрын

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

@laraibanwar1618 2 жыл бұрын

Brilliant Please make a video of suffix array which jnvloves nlogn solution Thnks

@priyankakothari3544 2 жыл бұрын

Understood Completely!!!👍

@abhishekraj8845 Жыл бұрын

teaches well understood well😊

@aarushirai6374 2 жыл бұрын

Understood. Really helpful.

@uchihaPrincessSakura 2 жыл бұрын

Watched it completly Raj Sir

@harshverma1221 2 жыл бұрын

For all those complaining for the background Striver also noticed that hence placed his photo just over that e

@rahulpothula1902 2 жыл бұрын

Perfectly understood!!

@sanbidrc 2 жыл бұрын

Great content as always. Btw How to insert "apples" AFTER inserting "apple". Wouldn't "apple" be lost?

@takeUforward 2 жыл бұрын

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

@gandhijainamgunvantkumar6783 2 жыл бұрын

Understood bhaiya. Keep making this type of amzing content :)

@nishant3904 2 жыл бұрын

UNDERSTOOD very well !

@ManishKumar-qs8xh Ай бұрын

You are the best, man!

@binitrajshah9354 7 ай бұрын

What if I insert "app" after "apple" and search word "app". As the p from apple is pointing to trie node with "l". Will searching "app" return true/ false? as we are returning this return node->is_end();