L2. Implement Trie-2 | INSERT | countWordsEqualTo() | countWordsStartingWith() | C++ | Java
Вставка
- Опубліковано 11 лис 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: First Video of the Playlist: • L1. Implement TRIE | I...
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/3qwT4OL
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 ☺️
FAILED TESTCASE ------- if a word doesn't exist but some starting letter exists for example "anuj " does not exist but 'an' does. in this case, when the erase function works, it returns, but decrements prefixes that should not be decremented.
@@anujtyagi4047 yes we just need to check if the word actually exists in the trie.
@@anujtyagi4047,
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!
@@ankursharma6084 To do this with O(n) space/time, iterate like you're going to erase the word, but push each node onto a stack. If you successfully reach the last node for the letter (and its word count is > 0, meaning you didnt happen on a prefix that matches the word to be erased), decrement that, then iterate the stack and decrement each node's prefix value.
The corner case I'm referring to is, say the word "apples" is in the trie, and you call delete on "apple". You actually don't want to allow that, so you need to ensure the 'e' has an 'endingWord' count > 0.
@takeUforward don't you think there is mistake in erase function bcoz you are decreasing count prefix but if in that path only that word is going till end then we should erase the node also ( link[ch-'a']=NULL) whenever we will find count prefix ==0 after decreasing it
remove funtiion in Node* should be like this
bool remove(char ch){
link[ch-'a']->cnt--;
if(link[ch-'a']->cnt==0){
link[ch-'a']=NULL;
return true;
}
return false;
}
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. 🤗
All test cases passed on my first submission. Thanks for e so explaining so well.
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
Understood!
Thanks you Striver!
It was really helpful!
I did it myself without looking at solution.
Thanks Striver
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
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!
ache questions mein MLE aayega
@ayushnegi4432 raja C++ ki duniya se nikal bahar. Java me ordered/unordered kuch nai hota, simple Map hota hai jis ka average complexity O(1) hai, baki khudse key ka structure wrong karega toh O(logn) toh hoga hi.
Raja agar Map use kar rha hai toh space toh badhegi na. Space complexity badhate hai taki Time Complexity kam ho
Map use karna galat nai hai, question kw constraint bht high ho toh extra space use karna hi padta hai
8-9 jagah spam nai kiya, jo code daal rhe the unko mera solution bataya taki discuss kare jaise tu kar rha hai discuss raja
Understood just awesome thanks a lot for this great content
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 😊
wow best teaching and clean code superb brother
you explained very easily. "understood"
Thanks bro, I have solved this ques of my own without viewing this video because of previous one.
what if the given word not present in Trie like applesauce is given for erase function???
So grateful for these videos
understood and thank you Striver.
I watched ur free ka tree series - the BEST on UA-cam undoubtedly covering lots of problems ! Hope u do same justice with this playlist also 😊
understood Sir. Thanks a lot.
11:10 Man, the energy ❤️⚡
Very well Understood bro 👍
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.
hey! but it says that we are erasing with the assumption that word does exist, otherwise we'll definitely have to make some checks
@@tripti_ Yeah!
@@yashsingh9121,
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!
Understood very well!
understood!! a correction, we can actually remove the nodes. But thankss...helped a lot
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?
Yes, we need to erase the node links as well.
For that we can use a stack and store all the TrieNode addresses .
Now pop the addresses and delete them until their prefix_counts equals 0
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.
Here ends actualy means complete word 😅
@@takeUforward,
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 to avoid partial deletion of characters.
Thus Map storing is much better option than endsWith!
super OP explanation sir Thanks alot..
sir, what if countEndWith becomes zero after deletion? The nodes are still there right?
isn't this a waste of memory?
Understood !! Raj sir you are just ab amazing teacher !
aur bhai.. nakli ayush
@@Whyush7 kya nakkli.. tu udhar bhi agaya 😂
Your playlists are great bhai
Tremendous effort given by the boss, understood as always :)
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?
how would you know what is the trie of l and s when it braches? can be both sides
21:38 initially i had had this doubt that we must check if it present or not but now clear
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
You can't, Vinayak. It was through a refferal.
@@RyanKOnk how you know it was from referral?
@@vinayakkumar5612 from Twitter space convo.
perfect explanation
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?
how do you make this Trie code work for both uppercase and lowercaase letters
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.
Same query, I think here we are assuming that the word we are trying to erase is a valid word which was inserted in the trie before, hence this solution works.
understood everything bhai.
understoooooooooooooood bhaiya. thanks :)
Striver, if there are duplicate entries, then deleteEnd() would merely decrement the count without removing the expected string entirely.
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 ?
I think you can do that .
Sir Why don't we increase the value ---> ew=0,cp=0 at the root node
I have one doubt when the word is not present prefix is present then it will delete the prefix count which will be wrong ?
Next level explanation bhaiya .Thank you so much for this amazing playlist.
Thank you 🙏
can anyone tell me why we are using endwith? can't we get same answer using prefix_counter because for all end nodes prefix counter and endwith will remain same. this is extra variable we are taking or I got wrong?
Amazing!!!!!!
Understood, thanks
Hi Raj , On website Both Link 1 and Link 2(Usually Leetcode question) are same .
Thanks Brother
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.
you can just add a little check before erasing the word
public void erase(String word) {
if (countWordsEqualTo(word) == 0) {
return; // If the word does not exist, do nothing
}
TrieNode node = root;
for (char ch : word.toCharArray()) {
TrieNode child = node.children.get(ch);
if (child != null) {
child.prefixCount--;
if (child.prefixCount == 0) {
node.children.remove(ch);
return;
}
node = child;
}
}
node.wordCount--;
}
this will do fine i guess
Felt soo good to know that you are joining one of the biggest IT firm.
But please dont leave us behind
thanks
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();
}
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.
Yeah so I tried Implementing a recursive function. May be you might find helpful
void newErase(string s){
Node *temp = root;
bool t = helper(s, 0, temp);
if(t){
cout containsChar(s[i])){
temp = root->get(s[i]);
temp->startsWith--;
t = helper(s, i+1, temp);
} else {
t = false;
}
if(t == false){
temp->startsWith++;
return false;
} else {
return true;
}
}
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
We are updating the CP in the link node of p and m so there will not be any problem.
waiting for next video in trie series, if there is any \o/
in java code 6th line is not needed na??? Anyone please elaborate it what is it's use and why it is not needed...?
Thank you so much mann, your explanation is just best❤🔥, thanks for this content!
Great sir 🥳
Please suggest any playlist for structure
understood
Java code link not working. Please fix.
if appleapp is inserted and we want to count words ending with apple your code gives 1 as output. please help in this regard
we should aslo maintain flag variable , so that we will know the end of the word
Understoodddddd sir ji!!!!!!
Plz drop a oops series in c++ anna..
Understood!
Thanks Striver
🔥
Understood ❤
understood😊
Thank u so much for the awesome explanation. You are the best.🔥🔥
Understood!!!
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
}
};
understood ❣
Understood SIRR!!
Understood.
Understood 🙌
Understood 👍
Eagerly waiting for next videos eksat upload kardo sare 8 videos.. Aaj kal me..
Areh ye chuswaha dimag ka dahi kr k rkha hai 😂
@@takeUforward ik par ab dhyan mat do..
✌
Padenge likhenge banenge nawab.
If Arnab Goswami was a DS Algo teacher
Understood 🙂
uderstood bhaiya
thank you bhaiya
Understood!
memory leak in the erase function
Understood:)
UnderStood🙏
Bhai please make the DSA series in hindi language also 🙏
understand
🤩