Hello, everyone.
So in this video, we are going to discuss that we have discussed this problem in our last video and
we discussed the two disadvantages of using that solution, the world map.
So what we are going to do is now we have advanced our problem.
So now we have a collection of words and not just a single word.
For example, the good word is containing Lion the King and not a lion only.
Similarly, that the word is containing the word tiger, the competitor, and not only the tiger.
Similarly, Inocente leopard and dangerous shock and large logevall.
So what do you need to do in the paragraph?
Lion the King.
So Lion the King is present here and Lion the King is present here.
So you are going to replace this entire three words with the word cat.
So similarly, you are going to replace the word innocent leopard with the word cat, and similarly
you are going to replace the word Logevall with the word Oshin, and they will not replace Shakar because
the word is dangerous and not only the shock.
So that is the problem statement.
And I told you what they can do.
We can use Debrided as a teacher here.
So basically what we can do, we can use tried it as a teacher here and how I am going to throw the
words and try.
That is the important thing.
So I will told like this.
I have the root node for a try.
Let's take one word, for example, if I want to store Logevall so I will store large first.
So L then a.
And keep going on.
I will also store the character space bill, so I am going to store the blue, which is correspond to
Will and I was told the last character is E, so e.
Will stole a lot of things.
First of all, it is basically a terminal node, so I'm going to highlight this node and what else evil
stole evil also stole the key.
Evil also stole the key here, which is OCN, so you need to modify your Naude.
And your note will contain is terminal U.A. will contain area of this exercise and you will contain
one more.
Uh, let's Namadgi only string key so you will told you need to modify your node and you will store
one more data member, which is string key.
And this terminal node, this terminal node is going to store the key, which is, Ossian, if you remember,
I have discussed a similar application before and the application was Truecaller up, if you remember
to call a rep.
So I told you in that case what I will do.
So let's say this number belongs to a person, John.
So the last character, the last a. was starting the world, John.
Distorting the name John, so similarly, we are doing exactly the same here, the last basically the
last inaudible question.
Similarly, you can enter the word dangerous dog.
So de.
Then dangerous, then space, then basically shark, and similarly, the last character, Turkey will
store ocean.
And obviously, this is the last character to come in 11, so we are going to highlight this, and in
this way you will insert all the words, you will insert the king.
So we will insert line then space.
I have space here.
So we will insert space.
Then you will insert the so you will insert the then space.
Then you will insert king.
And we will store basically get.
So that's how your trial will look like.
Right, and what you need to do, you need to do this preprocessing only one time.
Once your tribe is ready, what do you need to do?
You need just you just need to iterate over this paragraph and start replacing the word, start searching
the word and try and start replacing them.
So we are going to construct this tribe only once and then, oh, basically, we will call the error
function only once by once, meaning for inserting all the words after we have inserted all the words,
our function will not be used.
We will use only the search function.
Right.
We will just write it over the paragraph and we'll simply call the function search.
So for example, let's take this example, Lion the King.
So I will start from L..
Yes.
At this present.
Next character line.
Yes.
Linus present.
Sorry, this is line.
So line is present.
This present king is present.
So at atlast you will be able to find King G.
So just G I will replace the entire this word with Cat and I will move ahead to the word K then I will
check escape as in no case not present then simply move to the next word.
Right.
So check I is present innocent.
Yes I is present.
We are going to insert this so we will replace everything.
Similarly for large wheel I will start from L and then we will be able to find out at E.
I have this option so I will replace this with Océane for please be so ps not present here.
Don't do anything.
Move to the next word.
W is not pleasant.
Move to the next world s s is not present.
Move to the next world.
So you can see we are able to optimize our algorithm.
Our search function has been optimized and it's really, really fast now.
And with the help of prioritization, we have solved all the two problems that we have with the previous
approach.
Right.
We have a collection of words is working properly.
Try is the best solution if you have a collection of words.
So that problem is solved.
And second problem was the memory problem.
Right.
And it will not take a lot of memory at Max.
At each level.
You are going to have a twenty six word array right at Max.
You are going to have 26 words for twenty 26.
At Max you can have twenty six node for each node, 26 child in order for each node.
And what can be the depth, what can be the depth of this.
Try so depth can be the largest number of characters.
For example, we have a collection of words, so in this case four, then three and then four.
So around around thirteen characters.
So, so that will not be a problem.
So this is this is taking very little space.
This is taking very little space as compared to the previous approach.
So we have solved both the two problems, the memory problems and the single word problem.
So this problem was basically asked by the company Adobe, one of my friends interviewed for the emptiest
job member of technical staff job for the lobby.
And they got this problem in this first round.
So they didn't ask them to write the code, but they just ask them the complete solution, starting
from the previous video, the reverse solution.
But the problem with that reverse type solution and then let's try a solution, they just ask the approach.
And they didn't ask him to write the code.
So knowing the approach is sufficient for this problem, writing the code for this problem is is not
an interview task because for interview, we have only limited time, 45 to 60 Minutes, and this problem
cannot be coded in that time.
We also need to discuss these approaches.
They are pros and cons.
You will not be asked to write the code for this problem.
The interviewer just asked you the approach and not the code.
So I think that's all that I want to cover in this video.
So, again, if you face any problem in understanding the solution or if you have any other problem,
just ping me.
We are ready to help.
So that's it from this video, guys.
So I will see you in the next one.
Thank you.