Welcome back.
We have discussed the recursive approach for solving the edit distance question, and we have seen that
the space complexity for that solution was of the order of n plus M, and the time complexity was of
the order of three to the power n plus m.
Now, this definitely is not a great time complexity.
And let's see if we can do better.
So let's proceed with the memoization approach.
Remember memoization is just recursion plus storage.
So let's take a look at how.
By just adding a few lines of code, we will be able to memorize the recursive solution and arrive at
a much better time complexity.
For discussing the memoization approach, let's take an example.
Let's say we want to convert table to bell.
So we would need a 2d dp array.
And we have rows for every character in word one.
And we have columns for every character in word two.
Now of course you could reverse the position of table and bell, but again either way works.
Now let's write the indices over here.
So we have 012.
And over here we have 01234.
Now before we go ahead and discuss this approach, let's quickly discuss what each cell represents.
For example, what does this cell over here represent or what subproblem does this cell represent.
So this cell over here represents this subproblem where we have t e, b, l and b.
So that is what this subproblem represents.
In a similar manner.
This cell over here would represent t e and B or this cell over here would represent t e and b e l.
And again the approach in memoization is that we will compute a subproblem only one time.
And then we would store it so that if we encounter it at a future time, we would just return the value
in constant time and we would not have the need to compute it.
So again, the way that we will approach this is it's just going to be the same recursive approach.
But then initially we have every cell filled with minus one.
And whenever we compute the answer to a subproblem we will store it.
So whenever we have a call first we would check whether the value of that subproblem in the DP table
is equal to minus one or not.
And if we see that it's not equal to minus one, we will just take that value and return it.
And if it is minus one, we will go ahead and we will have recursive calls to compute that value.
But before we return the value we will go ahead and store it in the DP table.
So this is how we can memorize the recursive approach by just adding a few lines of code.
Now let's quickly take a look at the space and time complexity of the memoization approach.
So notice that the upper bound of the maximum number of computations that we would have to do is of
the order of n into n, where n and m are the lengths of the two words that are given to us.
Now, this is the case because at max we would have to do n into m computations, because that's the
number of cells that are there in this DP table.
And if we need a value that we had previously computed, we will not compute it again, but rather we
would just retrieve it from the DP table and return it.
So that's why the time complexity over here is going to be of the order of n into m.
Now, when it comes to the space complexity, it's going to be of the order of n into m plus n plus
m.
Now, we will use this much space over here on the recursive call stack.
And again we have discussed this when we discussed the recursive approach because this is the maximum
depth of the recursion tree.
But then between n m and n plus m n m dominates.
And that's why we can say that the space complexity of this solution is also of the order of n into
m.
And again, this space over here is used for the DP table.