Welcome back.
So this is the recursive solution that we have previously written for solving the edit distance equation.
Now let's go ahead and memorize this.
And you will see that for achieving this we will just have to add a few lines of code.
All right.
So let's get started.
To start with let's create a 2D DP array.
And let me just call it memo okay.
So this is going to be a 2D dp array of size n into m.
So I can say this is equal to array dot from.
And over here I have linked N because we want n rows over here okay.
And we want m columns okay.
So over here we'll have array and the size is m.
And we will fill every cell in this 2D dp array with the value minus one.
And this is something that we typically always do in memoization solutions.
All right.
So we have created our 2D array.
Now let's slightly modify the helper function which is the number of operations function over here.
So after the base case before we proceed over here which is the recursive case.
And before we do these computations we will go ahead and check whether we had already previously computed
this particular subproblem, which is the case where we have the particular values for index one and
index two.
So what we will do is we will check over here if memo at index one.
Index two is not equal to minus one okay.
So if it's not equal to minus one it is not minus one because we computed and stored it because over
here notice we had initially filled every cell in this 2D array with the value minus one.
So if it is not minus one we don't need to go ahead over here and compute it.
But rather we will just return memo at index one.
Index two okay.
And that's it.
Now let's go ahead and take a look at this part over here.
So if this is not the case that is if we had not computed it earlier we come over here and we check
whether these two characters are equal.
And if they are equal we do whatever we have written over here.
Okay.
So that's still the same.
But instead of returning it we are going to first store it.
So over here and say memo at index one.
Index two is equal to whatever we get over here okay.
And if this is not the case we compute insert delete and replace.
And we find the minimum between them.
And we store it in memo at index one.
Index two.
All right.
And then we'll just have to return it.
So let's go ahead and return it.
And again over here notice this is happening.
If these two characters are equal.
And because we don't have a return statement over here, we would need an else statement because we
don't want to calculate, insert, delete and replace in case the two characters that we are comparing
are equal.
So let's copy this and let's put it over here.
All right.
And then finally we would have to return memo at index one.
Index two.
And that's it.
And we have successfully memoized the recursive approach that we had previously implemented.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's working.
It's passing all the test cases.
So this is the memoization approach for solving the edit distance question.