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

See the enthusiasm !! See the energy of Striver while teaching!! Aur Kunaal bolta hai ki padhaane nahi ata 🙂.. I have learnt almost all the concepts of DSA from your free videos.. best source best channel.. favourite as always 💫

After struggling in the previous question for hours and watching the video three times, I wrote the code myself for this question after understanding the approach behind it. Thanks Striver !!

OMG!!!!...Just one day ago, I just knew the term "Trie" and today, after seeing Lecture 1 of this series, I am able to solve this problem just after listening about the approach for the insert operation only. You are real boss man...Hats off !

I really like the code quality of the code you write. This is the best resource in my opinion! Thanks a lot!

"UNDERSTOOD". Your enthusiasm in teaching boost the learners. Thanks a lot. 🤗

You are amazing bro the style you approach the problem and your explanation is just ohh there is no word to say keep doing this effort Really really greatful to you

All test cases passed on my first submission. Thanks for e so explaining so well.

Understood! Thanks you Striver! It was really helpful!

I did it myself without looking at solution. Thanks Striver

Understood the explanation. Haven't watched the coding part as yet since I want to try it on my own.

Understood bhaiya you are just awesome we are very lucky to have you 😊

Understood just awesome thanks a lot for this great content

Instead of having a endsWith property for each trieNode, we can have a static Map wordCounts which has word as key & its count as value. Whenever you have completed a word, just increment its count in the above map instead of incrementing endsWith. Eg: Map = {"apple" : 2, "apps" :2} Advantages of Map: Now for 3rd functionality i.e countWordsEqualTo(), we don't have to traverse Trie, instead we can simply check word in Map and return its count thus reducing TC from O(N) to O(1). For 5th functionality i.e erase() function we can just check if word exist in map, if yes then only we will traverse trie and reduce prefixCount for each character. If not then we simply return and the issue pointed by you is resolved. Thus Map storing is much better option than endsWith!

wow best teaching and clean code superb brother

In the erase function , it will be better to first iterate once over the word, to check if it exists or not. We can possibly take a flag to check that. If exists then go again once more to reduce counts. This way code will be more robust to user mistakes and we don't need to assume that word asked to be erased always exists in trie. Also , I think Striver uses term Create a new trie every time , which is basically a new node. Trie is only 1 , it's just new reference nodes of that trie that we create every time. See the complete version :- #include using namespace std; struct Node{ Node* links[26]; int cntEndsWith = 0; int cntPrefix = 0; bool containsKey(char &ch){ return links[ch - 'a'] != NULL; } void put(char &ch , Node* node){ links[ch - 'a'] = node; } Node* get(char &ch){ return links[ch - 'a']; } void increasePrefix(){ cntPrefix++; } void increaseEnd(){ cntEndsWith++; } void decreasePrefix(){ cntPrefix--; } void decreaseEnd(){ cntEndsWith--; } int getEndCount(){ return cntEndsWith; } int getPrefixCount(){ return cntPrefix; } }; class Trie{ private: Node* root; public: Trie(){ root = new Node(); } void insert(string word){ Node* node = root; for(int i=0; icontainsKey(word[i]) ){ node->put(word[i] , new Node()); } node = node->get(word[i]); node->increasePrefix(); } node->increaseEnd(); } int countWordsEqualTo(string word){ Node* node = root; for(int i=0; icontainsKey(word[i]) ){ node = node->get(word[i]); } else return 0; } return node->getEndCount(); } int countWordsStartingWith(string word){ Node* node = root; for(int i=0; icontainsKey(word[i]) ){ node = node->get(word[i]); } else return 0; } return node->getPrefixCount(); } bool erase(string word){ if( countWordsEqualTo(word) == 0 ) return false; Node* node = root; for(int i=0; iget(word[i]); node->decreasePrefix(); } node->decreaseEnd(); return true; } }; int main(){ Trie t; t.insert("apple"); t.insert("apple"); t.insert("apps"); t.insert("apps"); t.insert("apxl"); t.insert("bgmi"); cout

you explained very easily. "understood"

Thanks bro, I have solved this ques of my own without viewing this video because of previous one.

So grateful for these videos

11:10 Man, the energy ❤️⚡

understood Sir. Thanks a lot.

understood and thank you Striver.

Very well Understood bro 👍

I watched ur free ka tree series - the BEST on KZfaq undoubtedly covering lots of problems ! Hope u do same justice with this playlist also 😊

Understood !! Raj sir you are just ab amazing teacher !

Understood very well!

understood!! a correction, we can actually remove the nodes. But thankss...helped a lot

Your playlists are great bhai

21:38 initially i had had this doubt that we must check if it present or not but now clear

super OP explanation sir Thanks alot..

Hey Striver! In the code for erase function, we should not write the if else condition, as let's say the ith char is not in the trie but all the chars from 0 till i-1 were there, then what we doing is we are reducing the prefix count there which we shouldn't as the word doesn't exist. We should check before hand and if the word is not there we shouldn't do anything else we erase it.

Tremendous effort given by the boss, understood as always :)

perfect explanation

Won't we need to delete a node after erasing a word, if that node has 0 word ending and 0 prefix counts, to avoid memory leak?

Thank you 🙏

Amazing!!!!!!

understood everything bhai.

understoooooooooooooood bhaiya. thanks :)

Congrats for getting offer from fb london and google Warsaw...Can you share the full procedure about how you make it there!! How you got offer from there and how we people can join after being from tier 3 clge

what if the given word not present in Trie like applesauce is given for erase function???

To check if a word ends with a given suffix, I believe we must create a Suffix Tree. Not very sure how your CountWordsEnd() works here. Any help shall be much appreciated. Thank you Striver.

Thanks Brother

Understood

understood 👍

Understood, thanks

understood!!

Great sir 🥳

Next level explanation bhaiya .Thank you so much for this amazing playlist.

Thanks

Understoodddddd sir ji!!!!!!

Understood ❤

Thank you so much for such an awesome explanation bhayya. I am having a small doubt can we increment the countPrefix of the root node every time we are inserting a word ( any word ) so that we can get total number of words that are actually present in our trie ?

thanks

understood😊

understood ❣

Understood!

(Space Optimisation) Erase function with delinking of not required nodes public void erase(String word) { TrieNode cur = root; for (char el : word.toCharArray()) { TrieNode next = cur.get(el); next.decrementCharCounter(); if (next.getCharCounter() == 0) { cur.put(el, null); return; } cur = next; } cur.decrementEndCounter(); }

sir, what if countEndWith becomes zero after deletion? The nodes are still there right? isn't this a waste of memory?

understood

Thanks Striver

uderstood bhaiya thank you bhaiya

Understood SIRR!!

🔥

I have one doubt regarding endswith function at 11:28. For ends with you are starting the trie from the first character. But what if we consider words such as Dapps, or Mapps. Where the first character doesn't start with 'a', in this scenario, the given function fails. Can you clarify on that once?

Understood 🙌

waiting for next video in trie series, if there is any \o/

Striver, if there are duplicate entries, then deleteEnd() would merely decrement the count without removing the expected string entirely.

Understood 👍

Understood!!!

Thank you so much mann, your explanation is just best❤‍🔥, thanks for this content!

Thank u so much for the awesome explanation. You are the best.🔥🔥

Understood!

Understood.

Understood 🙂

Understood:)

OP!!!!

I think there is a small mistake in erase() function. We are going on decreasing the prefix but if we dont find a letter in the middle we are returning directly which means the letters which we have decreased so far will have wrong count. We need not check if that letter is present or not. The word which we are given for erasing will be definitely present in the Trie.

The erase word will reduce the prefix even when the word never exists in the trie. So , i think you should check if the word actually exists in the trie and then erase it.

Understood sir

🤩

Eagerly waiting for next videos eksat upload kardo sare 8 videos.. Aaj kal me..

UNDERSTOOD

Understood :D

❤

Here in you code for erasing we are returning when the ith character of the string is not found in the trie, but isn't there a problem with the count of the prefix .Since the word was not present and we updated the prefixcounts for the trie nodes. I think the soln should be dfs based in which if the word is found we return along the path and then reduce the prefix count.

UnderStood🙏

Plz drop a oops series in c++ anna..

If Arnab Goswami was a DS Algo teacher

Simple Implementation without alot many functions: #include struct Node { Node *links[26]; int endw = 0; int CountP = 0; bool contains(char ch) { return links[ch - 'a'] != NULL; } Node *put(char ch, Node *node) { links[ch - 'a'] = node; } Node *get(char ch) { return links[ch - 'a']; } }; class Trie { public: Node *root; Trie() { root = new Node(); } void insert(string &word) { Node *node = root; for (int i = 0; i < word.size(); i++) { if (!node->contains(word[i])) { node->put(word[i], new Node()); } node = node->get(word[i]); node->CountP++; // count prefix } node->endw++; // word completed } int countWordsEqualTo(string &word) { Node *node = root; for (int i = 0; i < word.size(); i++) { if (node->contains(word[i])) { node = node->get(word[i]); } else return 0; } // if(node->getEnd()) return node->endw; } int countWordsStartingWith(string &word) { Node *node = root; for (int i = 0; i < word.size(); i++) { if (node->contains(word[i])) { node = node->get(word[i]); } else return 0; } // if(node->getEnd()) return node->CountP; } void erase(string &word) { // word always exist Node *node = root; for (int i = 0; i < word.size(); i++) { if (node->contains(word[i])) { node = node->get(word[i]); // will contain node->CountP--; // removing characters } else return; } node->endw--; // word removed } };

Superb content ;) #striver

understand

how would you know what is the trie of l and s when it braches? can be both sides

Felt soo good to know that you are joining one of the biggest IT firm. But please dont leave us behind

in the fucntion erase, the statement "reducePrefix" must be before the get(word[i]) because we need to reduce the prefix for all node, including root. Can you explain more about this? Firstly, am I even right?

striver u beauty big bro

How do we update CW & CP , if more than one letter is there in node. eg : if words are apple and ample. Second node will have letters p & m ..CP for both must be different

Hi Raj , On website Both Link 1 and Link 2(Usually Leetcode question) are same .

Bhai please make the DSA series in hindi language also 🙏

how do you make this Trie code work for both uppercase and lowercaase letters

Sir Why don't we increase the value ---> ew=0,cp=0 at the root node