Welcome back.
Let's now get into the code for this space optimized tabulation approach for solving the edit distance
question.
So this over here is the code that we had previously written for implementing the tabulation approach
for solving the edit distance question, but for the space optimized approach, as we have discussed
in the previous video, we will not be using a 2D DP array, but rather we will be using two one dimensional
arrays.
Let's call it prev and curr.
Okay.
And both these arrays will have the size m plus one.
And we will just fill the value zero in every cell in both of these arrays.
So let's go ahead and do that.
So we have prev and then we have curr okay.
And both of them are arrays of size m plus one.
And we have filled the value zero in every cell in these two arrays.
Now let's proceed.
Now we would not need this part over here which was earlier used to initialize the first column okay.
So let's remove this.
But we would still need to initialize the first row which in this case is equal to prev okay.
So we have done that.
Now let's proceed with the iteration.
So over here we have this loop for I okay.
So I goes from one up to n.
Now as we keep going from one row to the next row okay.
We would have to implement a line of code over here which takes care of filling curve at zero.
Now earlier that was taken care when we iterated through the cells in the first column and we initialized
it.
But we have removed that part of the code over here.
Right.
So over here we don't need to initialize many cells, but just the first cell of car at every instance
whenever the value of I changes.
So let's do that.
So over here we can say car at zero is equal to I okay.
So that takes care of it.
So for example visualize it in this manner.
Let's say a row was the row with the index two when we implemented the 2D Depee tabulation approach
okay.
In that case the first cell in that particular row would have the value two.
But now we just have car right.
And we still need the value two over there.
And that's what is taken care over here.
Now once that is done we proceed as usual.
We check whether the two characters are the same.
If they are the same, then over here we have DP at I and instead of DP at I, we replace this with
curve.
So that's what we have to do, right?
Wherever we have DP at, I will change it to curve and wherever we have DP at, I minus one will change
it to pref.
So that's how we can implement the space optimized tabulation approach.
And you can see that's the case over here as well.
So we have DP at I minus one.
So let's change this to pref.
And we have DP I minus one over here as well.
So let's change this also to pref.
And we have uh over here DP at I.
So this changes to cur.
And finally we have DP at IJ over here.
And that changes to car at J.
Okay, so wherever we had DP at IE, we changed it to Kur and wherever we had DP at I minus one we changed
it to pref.
So that's what we have done over here.
Now let's proceed.
And one more important thing that we have to do over here is that whenever we are done iterating through
the respective values of j for a particular value of I, we have to make a copy of cur at that particular
instance and assign it to pref.
Okay.
So let's do that over here.
So prev is equal to and we make a copy of cur and assign it to pref.
So in this way we update the previous array to be the current array at this point okay.
And then we proceed.
Now once we are out of this for loop we will just return prev at m.
And that's it.
Now you may think why do we return prev at m and not cur at m.
And for that let me give you an example.
And again before we discuss why that is required, let's also take a look at this scenario over here.
Because we assign we make a copy of Cur and assign it to prev.
Whenever we come out of this for loop, prev will have the values which are equal to the latest value
for cur.
Okay, so that's the general case and therefore private M should work.
But again typically you may want to return cur at m because it was written depee at n m.
Right.
And again the reason why that would not work is because for an edge case it would cause a problem.
Like let's say word one is an empty string and word two has one character.
Okay, now, because of the way that we have initialized prev and cur, initially prev and cur would
have two elements and it would be zero comma zero.
So this is let us say cur and this is let us say prev.
And over here we have this for loop which initializes the values for prev.
So prev changes from zero 0 to 0 one.
For this example okay.
And because the length of word one is equal to zero, in this case we would not execute or enter this
for loop at all and directly we would come over here.
So if we were to return caret m we would be returning zero.
Which is wrong in this case because we do need one operation to make these two equal.
Right.
But if we do return private M it is correct.
We are returning one.
And this is correctly handled because we have initialization for prev over here.
So that's why we have to return private M over here to handle this edge case.
And again we have discussed why logically it is sound for the general case as well because we are making
a copy of Cur and assigning it to prev over here.
Now that's it.
So this is the space optimized tabulation approach for solving the edit distance question.
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.