So previously we have discussed the bottom up or tabulation approach for solving the edit distance question.
And we have seen that the time and space complexity were of the order of N into M.
And this is an iterative approach, whereas the memoization solution was a recursive approach.
Now let's come up with the space optimized tabulation approach for solving this question.
So let's get started.
Now this is the table that we filled for solving the question where word one was table and word two
was bell.
Now notice over here to fill every row we only needed values from the previous row or the current row.
So for example for filling this cell with this value we had to evaluate these three values.
Right.
Because this was insert this was replace and this was delete.
So we only needed these values similarly.
For example for filling this cell we only needed this value over here because these two were equal.
So we can observe that we only need to store the values at a previous row for computing the values at
a current row at any instance.
So finally, when we are computing the values in this row, we only need to store the values in this
row, which is the previous row.
And we would not need to store all these values in this way.
We can just have two 1D arrays of size m, where m is the number of characters in the word that we are
keeping over here for columns.
Now, we could even optimize this in a better manner by checking which among the two words that are
given to us is of lower length, and that could be kept over here to represent columns.
And in this way we could get a space complexity, which is of the order of the minimum between n and
m, where n and m are the lengths of word one and word two, respectively.
So the space optimized bottom up approach has a space complexity of the order of the minimum between
N and M, and the time complexity is still of the order of N into M, because we would still have to
go through each of these cells till we arrive over here, which gives us the answer.
So this is the space optimized bottom up approach.
Now we would need to erase curr and prev.
And we would use the values at prev to find the values in a current array.
And then when we proceed to the next array for example let's say we had this over here, these values
over here at prev in the prev array.
And then we use that to calculate these values which would be the curr array.
Then we would move ahead and try to calculate these values.
And we would change the values in the prev array to the curr array at this point.
So this would become the new prev and this would be curr.
And once we are done computing these values this would be changed to prev.
And this would become curr.
And we would compute these values.
And once we are done this would be changed to prev.
And this would be curr.
And we would compute these values.
And finally this would be changed to prev.
And this would be curr.
And we would compute these values.
And we will get the answer over here.
So we have discussed four approaches for solving the edit distance question.
And we have seen that for the space optimized bottom up approach, we had a time complexity of the order
of N into M, and the space complexity was of the order of the minimum between M and N, which is even
better than the simple recursive approach for solving the edit distance question.