Hello, everyone.
So in this video, we are going to cover one more question, and the name of the question is Chartist
unique prefix.
So what is the question?
So we will be provided with a list of words.
So these are list of words.
I have zebra dog, dog and of and what we need to do, we need to find out a prefix.
And that perfect should be unique as a short list.
And from that prefix we should be able to represent each word in the list.
So for example here, if I take four zebra, if I take only the first character.
So from the I can uniquely identify as zebra.
Yes.
Four short for dog.
If I take only the first character which is D so from the can I uniquely identify dog.
No.
Why.
Because is the prefix for dog, duck and dove.
So I need to take the second character also.
So from do, can I uniquely identify dog.
No.
Why.
Because Due is coming here as well as do is the prefix for the word love.
So if you take the third character G so from Dog I can uniquely identify the given word.
So in this case, the prefix, the shortest common prefix and the word, they both are same.
Now let's talk about character three so I three which is dog.
So for Duck, if I take the word B again, this is not unique prefix from the.
I cannot uniquely identify that because this is the prefix for this as well as for this.
If I take you so from the you can uniquely identify dog.
Yes.
The EU is coming here only here, so they use the prefix for this.
Now let's talk about the fourth word, which is.
So if I take only the these coming here, here and here.
So it's not unique.
We cannot uniquely identify a word, though, from the similarly, the EU deal is also the perfect for
dog, so I cannot uniquely identify those from do so.
I need to take the third character also, which is V, so from the Ovie I can uniquely identify because
the DV is only prefix is the prefix that is appearing here.
So that's the question.
So given a list of words, we need to find out the prefix and the prefix has to be unique as well as
chartist to represent each word in the list.
So now the question is how we can do this in the most optimal way.
So the answer is basically by the help of provided a structure.
So how private sector will help us here?
So let's do one thing.
Let's try to insert all the characters in a try.
So what we will do is try.
First of all, we have a root node.
No.
Let's say I'm inserting.
This word Xebra, so I will modify my trial, that's structure, how I'm going to modify it.
So initially I used to have only two things right.
If you remember, the first one is basically a variable, which is of type is terminal.
And second was basically a tile area of the success rate area, a trial area of size 26.
What I will do, I will take one more variable.
I will modify my route node, I will modify my node structure.
I will take one more variable int count.
Now, why I am taking this very blunt count and how it will help us here, let's try to analyze so far,
but what I will do, I am inserting the first.
So this is not present.
I will insurgency and I will also need to update the value of this terminal.
That will be false.
Now, what will be the value of count?
The value of count will be how many times this node, how many times we are going to this node.
So.
I'm coming to this node for the first time, right?
I am coming to this node for the first time, so the count, the value of count will be one.
And obviously, terminal is basically false falls, and this initially, all the values will be null.
Now the second character is E, so I will make a. e and since we are coming at this node for the first
time, so the count is one now, similarly for B, I am coming for the first time.
So the count is be solid.
So they counted the count for this one now.
Similarly for I am coming for the first time at this nodes, the count is one.
And similarly for a I am coming to this node for the first time.
So the count is one.
And also this note is our terminal load.
So it must be highlighted basically is terminal will be true for this node.
Simple.
Now let's talk about the second character, the second word, which is dog.
So again, I am coming to be for the first time.
So the count will be one, not the next word is, oh, sorry, the next character is oh.
So I'm going to over the first time.
So the count is one.
Similarly, the count for the character G is one because I'm coming at this node for the first time
and also this is the terminal character.
So I will highlight this.
Now let's talk about the third word, which is duck.
So D Yes.
D is present here.
So what I'm going to do, I'm coming at this node for the second time, so I will update this value
to two.
Now, the character is you, so I'm coming to this note for the first time, so the count is one.
Now, the next see, so I'm coming at this node for the first time, so the count is one and four K.
Similarly, the count is one, also the character case, the terminal.
So we are going to highlight this.
Now, let's talk about the last word, which is Dove so far, Dove.
I'm coming at this node for the third time, so I will increase its value to three counties, basically
storing how many times you are coming to this node.
So I'm coming to node for the third time.
So that's why the count becomes three.
Now, the next year or so, I'm going to do this for the second time, so I will increase the value
to two now.
So V, I'm going to be this node V for the first time.
So the count is one.
And so similarly, I'm coming to this node for the first time to the counties one also this node is
a terminal load, so I'm going to highlight this node simple.
Now your tribe is ready.
And now let's see how this tribe will help us in finding the answer, finding the prefix which is shortest
as well as unique.
So what I'm going to do is let's start with the first word.
Let's start with the first word, so the first word is basically.
The first word is basically is zebra, so I will start searching the word zebra in the try.
OK, so this was basically what I've done till now.
I'm calling the ER function, I'm calling the er function for these all forwards and in the er function
what I have done.
I'm also setting the value of variable count.
We also need to set the value of variable count.
So you need to modify the ER function accordingly.
No.
For finding out the prefix we are going to call this search function, and similarly, you will also
modify a search function, how you will modify Lizzi.
So for Xebra, first of all, to come to this node Z and the count is one count is one, that means
this node is coming only for the first time.
So you will stop here and you will return your answer, which is Z.
So your answer for this word is basically Z.
So what you need to do in the search function, as soon as you find a word whose count is when you will
stop.
And that will be your answer.
So I will stop here.
My answer is, let's take one more example for Dog.
So I will go to this node D, go to this node and the count is three.
OK, so the count is three.
We need to move ahead, go to the node or so go to the node or or the count is to the count is not one.
So we need to move ahead.
So I will move ahead.
For G and G, the count, this one, as soon as you encounter count one, you will stop and that will
be a unique prefix.
So my unique prefix for dog is basically dog only.
Let's talk about the Third World, which is.
So again, I will come to this node.
I will come to this node and the count is basically three.
So the count is not one.
I need to move ahead.
So now I will go to you.
So for you, the count is one, as soon as the count is one, that means I'm coming at this door for
the first time.
That means it is unique.
I have come at this door only one time.
That means this is unique and you will stop here.
So you will stop.
And we will be until you announce will be the end.
You simple, right?
So you need to modify your search function.
And as soon as you encounter count one, you will stop.
Now let's talk about for this.
So you will start from D to the county's three counties, not one.
So you will move ahead.
You will go to the second character, which is all the counties to you will move ahead.
The third character is V, so you will go to V and the count is one.
Count is one, and you will stop here, so the answer for this is the of which is the right answer.
So that's how I try to help us, right?
So these are the answer and our answer are basically correct.
So what you need to do, you need to modify.
First of all, you need to modify, you know, class and the lower class.
You will have one more day to remember, which is count.
Then you will need to modify the error function in which you need to modify the value of count, and
then you need to modify your search function.
As soon as you encounter an order with value, one with the count one, you will stop.
And that will be your answer.
Simple, right?
So that's how the trial structure will help us in this problem.
Now, the problem arises when the interviewer sees.
So if the interviewer says you cannot take one more variable, taking account variable is not allowed.
You can have at most two data members, which is is terminal and you already.
So interviewer doesn't like this approach, although this approach is correct.
But he insists you to find out another approach.
He doesn't want you to use another variable and remember why.
Because this is of integer type and this is basically a four bytes.
So you're each node the size of each in order will increase by four bytes and introverted and one that
simply says, no, this is not allowed.
You cannot take more memory.
So now how can you use to try to structure in this case?
So let me it is everything and let me tell you how we can use try to judge in that case.
So introducing only two the members are allowed, which is is terminal.
And the second is basically you are adding.
These two are the only members which are allowed.
So, again, we need to modify our approach somehow so that we can uniquely identify the prefix and
how we are going to do that.
So what will you let us construct private sector again?
So this is our route node.
So initially, what is happening, the count variable, whatever the count variable is doing.
So it is containing only two things.
If you remember, the value of count can be one or it can be two three for anything else.
So if the value of count is one, I'm going to stop and I am going to return.
My answer and count of value is anything else.
Then it doesn't matter.
I need to continue searching.
Right.
So basically it seems like true or false typewrite.
If the value is one, then stop.
If the value is anything else, then continue.
So basically we can do the same thing we can we can use the variable is terminal for doing the work
of count.
How so?
For one, what we can do, we can use true and for the value we can use false simple rate discount what
it is doing if the value of count is when they need to stop at zero to continue.
Similarly, we can use the terminal data member to satisfy the to do the work of current variable and
how we can do that.
Let's see.
Let's see how we can do that.
So what I'm going to do is so let me draw the tray for you, and this is our route node, so I'm inserting
the characters.
And since I'm coming at this node for the first time, I will set the value of its terminal to be true.
So if you remember in the previous approach, I was setting the value of count to be one.
If I'm coming for the first time here, what I doing?
I am setting the value of its terminal to be true.
For the first time and for the rest of the times, the count will keep incrementing two, then three,
then fourth and fifth and sixth and seventh and eighth.
And for this case, what I will do, I will instead of true, I will change its value to false.
That is the approach that we are trying to do here.
So for me, I'm coming at this moment for the first time, for the first time, if you remember.
What is the approach for one I am using.
True.
So I will set the value of time to be true then.
Similarly for B, I'm coming at this not for the first time, so that the value to true then similarly
are I will set the value true.
Similarly for a I will set the value to.
Let's insert DOJ Asep Sordi going for the first time through or coming for the first time, the value
of this terminal is through G coming for the first time, the value of its terminal is through.
Latins are the third way, says Doug.
He'll be coming for the second time.
You are coming here for the second time.
So for second time, what they will do, you will change the value to false.
So I will change the value to false in case of variable.
I used to increment these values, but in case of using this terminal, I will change the value to false.
Now the next is due.
So you I am going for the first time.
So true.
See, I am coming for the first time through next character is key, I am coming for the first time,
so the value of this terminal is true.
Now, let's move on to our last word, which is love.
So again, here we are coming for the third time.
So the value of so the values already fall.
So, again, we can change it to fall.
Now, the next year or so, we are coming here.
The value is true.
We will change it to false.
Now the next is V, so V doesn't V is coming for the first time.
So I will change the value to true.
Now he's coming for the first time, so I will tell you to do so again, but need to do you what are
you doing?
You are basically modifying your air function, right?
You need to modify the air, the function of tri.
For setting the value of Istomin and now let's talk about searching to find out the answer.
So for Xebra, what I will do.
So go to this node and it is true, true, true means you have come here only one time.
You have visited this node only once.
That's why I have to here.
That means you need to stop.
It is exactly like if the value of count is one.
You have visited this not only once.
Similarly, if the value of e-mail is true, you have visited this not only once since we have visited
this, not only ones.
That will be your answer.
OK, so you will stop here.
Your answer will be easy for dog.
Let's see what will be the answer.
So you will come here and the value is false.
So you will move ahead.
You will come here and the value is again false.
So you will move ahead.
You will come here and the value is to the values.
True.
Yeah, we will stop here.
So the answer is dodgy.
Now let's talk about Doug.
So you are coming here.
And the value is basically false.
That means you will move ahead.
So you will move ahead and the value is to the values, to you will stop.
So the answer is do you?
Let's talk about our last word, which is love.
So you will come here.
The value is false.
You need to move ahead.
You will come here.
The value is false.
You need to move ahead.
You will come here and the value is true and you will stop.
So your answer is Dovi.
Right.
So in this way, you will be able to find out your answer using the use if you you need to modify the
search function and you will able to find out your answer.
So the work of the variable count can easily be done by the variable rate.
So this is how trials can help us here.
And you can also see so the last law is basically storing the true value, right, because obviously
this since this is the last node, it has to be true and they are storing true values.
Now, one more doubt, if the person can have is basically, uh, for example, if I have a word dog
and if I have if I have a word doggy, then with the prefix for this, because the prefix cannot be
dog because dog is coming here also.
So in this case, this is basically invalid input.
OK, so this is not a valid input, this is invalid input.
So these type of cases will not be presenting it in.
You do not need to worry about that.
OK.
So this type of input will not represent only the valid inputs will be there.
And I have discussed two approaches.
One, if you need to modify, if you are allowed to modify, you are allowed to take extra memory.
And if you are not allowed to take extra memory, then modifying the using the established member for
the four for doing all the work that count variable was doing that.
So you can use pride as a teacher in this problem.
And this problem was asked in Google, according to this website.
So yeah.
So what you can do, you can try coding the solution yourself.
I have discussed two approaches and you can write the code for one, the approach.
And if you are extra hard working, then you can write the code for both the approaches.
And if you face any problem in writing the code or if you are not able to understand the solution,
will free to bring me out and give in section.
So that's all that I want to discuss in this with guys.
So this is from this video.
I will see you in the next one.
Thank you.