Hi, everyone.
So in this video, we are going to solve this question at a distance, so what is the problem statement?
So what we need to do so given two words, word one and word two, so we need to convert word one into
word two and allow the operation is we can insert one character in word one.
We can delete one character from word one, we can replace one character from word one.
And our ultimate goal is to convert word one into word two.
And we need to find out the minimum operations.
Right.
We need to find out the minimum number of operations.
And these are the three operations that we have inserted character in word one, the little character
from word one and replace the character from word one.
Let's take one example.
So I have this example.
The word one is horse, and I want to convert this word into arrows.
So the first step is basically replace it with R, so replace it with ah.
Now this is Aurora SC second step stabilising remove R so remove or remove means delete the character.
So now it becomes rwc and tardies basically again delete this character so null rules so it becomes
it to the word two.
So we three operations.
Right.
So we did the operation first is replaced and then to delete operations.
So the number of operations that period is three.
So that's why the answer for this input will be three.
Let's take one more example and let's try to understand.
So the second example that is given to us is basically we need to convert the word intention.
We need to convert the word intention to execution.
And the number of steps will be five, let's see what will be the step so far removed.
So after removing B, this will be my strength, i n n d I own.
The second is basically replace I with E, replace I with E, so this will be an NBA.
And now the third is basically replace and with X, so replace and with X, X N D Io and then replace
and with C..
So replace and we see it will become the new and the last is basically insert U.
So we will insert you here and it will become x, e, c you PICU and which is a close to this word and
with five operations.
So that's why the output will be five.
So I hope you have understood the question.
Now let's see how we can solve this question.
So it's pretty simple question.
We can easily use recursion here.
So how we will be able to use recursion.
Let's see.
So what we need to do, we need to convert word one into over two.
And these are the three operations allowed, we can insert one character, we can insert one character,
we can delete one character and we can replace one character.
And we need to find out the minimum number of operations.
So this is a pretty simple problem, but you need to do so, let's take this example only.
Let's take I want to convert this word fruit into, let's say, this word for unity.
So what you're gonna do is you will stand here, you'll compare the last character, will compare the
last character.
So the last character is same.
So what I will do, I will tell Dacogen to solve this problem and this problem.
Right.
So, again, if there is match, if there is a match, then we do not need to do any of the operation
because the characters are matching.
So if there is a match, for example, the length of this string is basically let's m and the length
of the string is basically let's say and then ready to do, we will call for M minus one and minus one
to simply call recursion, let's say added distance.
Let's say the name or the name of the function is minimum distance.
So what I will do, I will call the function minimum distance, string one and a minus one, string
two and and minus one.
Right.
Will pass this part.
Now if there is no match, so let's see if this character is a different calculated.
This character is now if matching is not there, the characters are not matching and they are different.
Now we have three operations, so we have three operation insert, delete and replace.
So what I will do, I will try to insert one character.
So for insertion, if I want to insert what will be my record, because it will be empty medium distance
string when M string two and minus one, this will be the insertion.
What will be the deletion?
The second option is I delete this character.
So the first option is insert the character here.
Second option is delete it.
So for deleting E, this will be string one and minus one, I will call the question on and minus one
string and it will be.
And now the third option is to replace replace character with the so replaced in case of replace your
recursion will be M minus one as two and minus one.
So these three will be recursive call if you are not able to understand.
Let me explain you again how these three will be directly Yancoal.
Let me write that example once again.
So the example was, you want to convert this world into this one.
Right.
So what I'm saying here is the last character is different.
So this is a necessity since they are different.
We have three options.
Either we will insert so by insertion, but I will do I will insert the character here.
So after inserting what I will do, I will call recursion like this.
The second option is I can delete these characters, do not insert just delete this character.
Then my reaction will look like this.
The third option is basically simply replace.
So instead of deleting E, you will simply replace it with T.
If you are replacing with D then your next location will be like this.
So that is, that will be a recursive call.
And what we need to do, we need to find out the minimum of all of them.
I have three option insert, delete and such.
We need to return the minimum number of operation.
So I will take the minimum of these three and I will add plus one because I am doing one operation.
Right, that I'm inserting, that I am deleting or I am replacing.
So I will add one plus minimum of these operations.
So it's pretty simple.
Directly jump into the code.
So let's start writing the code.
The name of the function is and minimum distance, what it will take, it will take one string as input
and the size of that string string to as input and the size of the string.
Now let's talk about the base case.
First base case is if string one is empty, string one does not exist.
So if string one, this does not exist and you want to convert string one interesting to, then you
need to insert all the characters of string to and how many characters we need to insert the number
of characters which are present in string to which is.
And so I will return and.
Second option is if the second string does not exist, so if the second string does not exist.
Second string does not exist means empty.
So if the second string is empty and you want to convert string one into an empty string, what are
you to do?
You know, to delete all the characters.
President String, when and how many characters are there characters out there?
So you will return.
And so what I'm doing.
So this will be so here what I am doing since Stringbean is empty, so you need to insert all the characters
of a string to insert all characters of a string to and ahead of our time doing since string two does
not exist.
So we need to delete all characters from string ones or delete all characters of a string.
When and how many characters are there.
Characters are there the sizes m so that is the best case now if the characters are matching.
So if as one of M minus one is equals to as 12, I am checking for the last character.
So last, if the size is M then the last character index will be M minus one and similarly for the second
string.
So if the last character Rasim, if the last character assassin then do nothing, just called the recursion
on the rest of the string.
So we will not do anything, it will be just simply calling the equation on the rest of the string.
Now if this is not the case then what to do.
I would answer will be written.
I have I have three option.
I have three options.
Either I will insert so far in such an empty string one as are discussed, this will be M this will
be string two and this will be and minus one.
This is the same call for the insertion.
Second is delete the character.
So this will be empty.
String one minus one, string two and minus one.
So at the end and the third option is replace the characters which are not matching.
So this is for replace.
This will be empty string when.
And minus one, string two and minus one.
So we are replacing the characters and what would be my answer?
My answer will be I am doing one operation, either insert, either delete, either replace, so one
operation plus the minimum of these insert comma, minimum of delete, comma, replace, and that will
be the entire code.
So if you are having confusion, let me write the full name here.
I'm inserting the characters.
Interesting one.
Here I am deleting the character from string one and here I am replacing the characters of String one
by a string to character.
So this is insert name of insert delete and replace and plus one because we did one operation.
So that will be the complete code.
And here you will simply call this function return empty string when what is sorry, this is word one
M so the site is basically word rendered size.
Second is where to and where to start, says.
So that's all, let's try to run our good.
So basically, our code is working, let's try to submit our code, so it is very obvious that we are
going to encounter a time limit extended because this is recursive solution.
So basically we are getting time exited and that is because our solution is recursive.
And so in the next we do what we are going to do is we will convert this recursive solution into DPN.
We will modify this code and we will use dynamic programming here.
Right.
So this is all from this video.
If you have any doubt, ask me in the Q&A section.
I will be more than happy to help you out.
So this is all from this video, guys.
I will see you in the next one.
Thank you.