L2. Implement Trie-2 | INSERT | countWordsEqualTo() | countWordsStartingWith() | C++ | Java

In case you are thinking to buy courses, please check below:

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.

-------------------------------------------------------------------------------------------------------------

[takeUforward]

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

[domod]

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 💫

[ltieysn]

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 !!

[sayandey]

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 !

[nagatanujabathena]

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

[amishasahu]

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

[dailydestress]

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

[aadharjain]

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<bits/stdc++.h>
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; i<word.size(); i++){
if( !node->containsKey(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; i<word.size(); i++){
if( node->containsKey(word[i]) ){
node = node->get(word[i]);
}
else return 0;
}

return node->getEndCount();
}

int countWordsStartingWith(string word){
Node* node = root;
for(int i=0; i<word.size(); i++){
if( node->containsKey(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; i<word.size(); i++){
node = node->get(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<<"Count of apple
cout<<"Count of apps
cout<<"Count of app

cout<<"Count of starting with app
cout<<"Count of starting with pps




cout<<"Count of apple
cout<<"Count of starting with app

return 0;
}

[abinashpradhan]

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

[jaisamtani]

Instead of having a endsWith property for each trieNode, we can have a static Map<String, Integer> 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<String, Integer> storing <Word, Count> is much better option than endsWith!

[sohamsen]

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

[TheElevatedGuy]

Understood!
Thanks you Striver!
It was really helpful!

[shindepranjal]

I did it myself without looking at solution.
Thanks Striver

[msteja]

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

[udaytewary]

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

[prashantmaurya]

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

[nagendramanthena]

wow best teaching and clean code superb brother

[sukhpreetsingh]

Understood just awesome thanks a lot for this great content

[abhisheksahu]

you explained very easily. "understood"

[yashsingh]

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.