Hi, everyone.
So in this video, we're going to do we are going to convert our exclusive called in to dynamic programming
code because this exclusive code is giving us time limit exited.
So we will use dynamic programming and let's see how we can use dynamic programming here.
So we can easily convert this recursive call entertaining programming.
So what I will do, I will create one tutelary because two strings are there.
So I'm going to convert, I'm going to create this to create this.
And I would answer with this one.
So our answer is going to be DPF and and and what DEPI of IJI represent so deep of IJI represent the
minimum distance minimum number of operations to convert Wordsworthian to work to by considering I correctors
my concerting I characters of words, one that is string one and considering the characters of string
two.
So that is the meaning of.
DPO Fidge celebrating myself, but DPO physically present DPF, I did at present the minimum number
of operations to convert string one.
Interesting to and considering I characters hosting and hosting when so going.
By this definition, my answer will be DPF Emelin, which will be the minimum number of operations to
convert Stenglein.
Interesting to by considering M characters of String one and end characters of String two, basically
by considering and digesting one and considering an entire string to write.
And I will start from zero and this will be the indexing m similarly zero and this will be.
And what will be the best case.
Best case will be if the string one is empty.
So if one is empty, how many operations will be required to convert string when adjusting to it will
be basically the size of string two that will be zero, one, two, three and so on.
Similarly, if the second string does not exist, what we need to do, we need to delete all the characters
from string one.
So again, 012 and so on.
Right.
This will be the best case.
And this recursive is very simple.
Right?
So let's just start writing the code.
So let me try it again for you, so what I'm trying to say here is my answer would be DPE of.
M and and and the best case that I was talking about is so if.
See if.
Let's talk about this index, right, so the value of a zero string one does not exist and this is G
rate.
So what will be the value of IJI?
The value of it will be first string is empty and second string is containing characters, right?
The value of a zero.
So first string is empty and the second string contains the character.
So what I need to do to convert string went into string.
Do you need to insert all the characters and how many characters are there?
Characters are there.
So this will be G so this will be G.
I'm repeating myself.
C first string is empty plate first string is empty.
Second string is containing characters.
I want to convert string when into string two.
So the only solution is insert all the characters of string to interesting when and how many characters
are there.
String two characters are there.
So that's Viji.
And similarly the posit for this.
If the value of JS zero and this is your IHI, then DP of IGY.
So what is G JS basically zero.
The second string string has two does not exist.
So in this case, what to do.
You need to delete all the characters from string one.
And how many characters are there i.e. characters are there.
So this will be, this index will be I.
That's why I write here like this zero, one, two, three and so on til and and similarly 012 tell.
And that's why I write this.
Right.
So let's start writing the code now.
So the code is going to be very, very similar to the recursive when you are just converting your recursive
solution into the solution.
So that will be pretty simple.
So what is M m is basically okay so let's first rename this too.
String S1 and the second is string as two Saudi.
The second is basically stating as to what is M m is basically a standard size.
And what is and is basically string to that size now you are creating one deputy.
The P5+1 and and blessin, because of Iran, said it will be the feminine.
So our answer will be DEPI of em and and because of Ejeta percent, we have discussed what the payoff
IJA represent.
I'm telling you again, so deep off, IJA represent the minimum number of operations to convert a string
one into string to by considering a character hosting one and considering the character hosting two.
So according to this formula out on Will Bill Feminine.
Now, what we need to do here.
Just simply, I trade all this debris to family values, so I equals zero.
I lost another close to em.
Four and J equals zero G less than articles to n g placeless.
Now, the best case that we were talking about, so if the first string is empty, then in that case
you going to insert all the characters of second string and how many characters are there characters?
Are there elusive?
The second string is empty, so if the second string is empty, then you need to delete all the characters
from string.
When and how many characters are there?
And when I characters out there in Stringbean in the elusive if there is a match, match means as one
of I.
Is it close to as two of G.
This is wrong.
I explained in our last video in the last problem that this will be minus one, so this will be minus
one.
So if that is the case, we can see so damaging.
If they are matching then you simply along and minus and minus.
And so that will be DPL.
Vijay will be.
Simple B of A, minus one and minus one.
Now, in the old part, if there are if the characters are not matching, so if the characters are not
matching, we have three operations, insert, delete and replace.
So what will be insert, insert will be DBF, I and G minus one.
What is the latest dip of a minus one and G and replace?
So what is replacer place will really be of I minus one and G minus one, like we have discussed all
this here I am doing exactly the same.
Right.
And finally, what will be my answer?
What will be my answer to my answer will be when?
Because we did it in the right place.
So my answer will be one plus minimum of.
Insert.
Mean you move out of these three, you going to take minimum, because in the question they are asking
us to report, our answer is the minimum number of operations required.
So that does it.
This will be you had an Paragould.
Late, this will be our and bad cold, so let's first run this score and then we will submit.
So our it is working fine now let's summit our goal.
And since this is a deep solution, so this will not encounter anti-American.
Yes.
So our code has passed all the test cases.
Right.
And now what is the time and the space complexity?
The time complexities.
Basically big famine you are trading.
Right.
And the space complexities you created this.
Deepti So space complexities.
Amann So this is the time and the space complexity for this minimum distance problem.
Right.
And this is pretty much very, very simple and it goes on relationship.
So if you have any doubt in this problem, do ask me.
So this is all about this problem.
I will see you in the next one.
Thank you.