Hey there and welcome back!
So far we have discussed the recursive approach and the memoization approach for solving the edit distance
question.
Now for the memoization approach, we have seen that the space and time complexity are of the order
of n into m.
And of course the memoization approach is a recursive approach.
Now let's get started with the bottom up or tabulation approach, which is an iterative approach for
solving the edit distance question.
To discuss the tabulation approach, let's take an example.
Let's say word one is table and word two is bill.
So we need to convert table to bill.
Now we will need a DP table of size six into four.
So the length of table is five and the length of bill is three.
Now if we were to add one to each we get six and four.
And this would be the size of the DP table that we need.
Now, as we discussed previously, this is a common approach when it comes to the bottom up or tabulation
approach to have an extra row and column.
So in this case also we would have columns for Bill and we have an extra column.
And we have rows for t e b l e.
And we have an extra row.
Now what would a cell over here mean.
So for example this cell over here is the subproblem where we have to convert T into B because this
is the last row over here and this is the last column.
So we would have to convert T to B.
And the number of operations required for that would be the value that we fill over here.
On a similar note, this cell over here would represent the subproblem of converting t e b l e into
just b.
Now that we have come up with the DP table required, let's also fill in the initial conditions in this
table.
So the initial conditions would be this row over here and this column over here.
Now notice that for example, this problem or this cell would represent converting an empty string into
the string B which would take one operation because we have to insert B to the empty string.
Right.
So in this manner over here notice that the initial values would be zero, one, two and three.
Because again over here we just have to convert an empty string to an empty string which requires zero
operations.
But over here we would have to convert an empty string to Belle which requires three insertion operations.
So these are the initial values that we can fill over here.
Now when it comes to the first column over here, the initial values are going to be 012, three, four
and five.
Because for example this problem this problem would mean converting t b l into an empty string which
requires four deletion operations.
So that's why we need four operations over here.
And in a similar manner here we would need two operations etc..
So we are done with filling the initial conditions.
And we have also come up with the DP table required.
Let's now proceed and iterate through these cells over here to get the final answer over here.
Because notice that this cell represents the problem of converting t e b l e into b e l, which is the
original problem.
So let's get started.
Now whenever we are comparing two characters in word one and word two respectively, as we have seen
previously, there are two possibilities.
One possibility is that the two characters are equal, and the other possibility is that the two characters
are not equal.
Now, if the two characters are equal, we do not need to do any operation.
So depee and IJ, when the two characters are equal, will just be equal to dp at I minus one, j minus
one.
So again for example, over here we see that we have e and e.
So when we are trying t e and b e.
So let me write that over here we are comparing e and e and we have t e and b e as the subproblem,
because that is what is represented by the cell.
And we see that these two are equal.
So we just need to consider these two or the remaining characters.
Right.
So we are reducing one character from word two which is j minus one.
So that's why we have j minus one over here.
And over here also we are reducing one character because of which we are doing I minus one.
So if the characters are equal depee at I j will just be equal to dp at I minus one, j minus one,
which is the diagonal element in the table visually.
Now, if the characters are not equal, then as we have discussed when we thought about the recursive
and memoization approach.
So if the characters are not equal, we have three options insert, delete, and replace.
So we need to identify the number of operations required to solve the subproblem if we are doing insertion,
if you're doing deletion and if you are replacing a character.
So we would have to compute these three separately.
And then depee at ij would be the minimum value among these three.
So again let's take a look at how to identify this from the DP table over here.
So we have insert we have delete and we have replace three possibilities.
Now a quick side note before we go ahead and compute this.
Now let's say we are trying to solve this subproblem over here which is t e b and b e.
Now, the point that I want to convey is that when we see that these two are not equal, let's say we
are trying to insert something.
So we insert E over here.
So we insert E on this side, not on this side.
As we previously discussed when we were discussing the zero to n recursive approach.
Because in the case of tabulation, we are going from the smallest possible subproblem till we reach
the original problem at hand.
So in this case over here for this cell the problem was t e b and b e.
So whenever we are inserting we are inserting over here.
And if we are deleting we are deleting over here.
If we are replacing we are changing this character to E.
So that was a quick side note.
Now let's go ahead and take a look at insert, delete and replace for the case where we are dealing
with this cell where the subproblem is t and b.
So we have t and b and we see that they are not equal.
So.
So when we are trying to insert we would insert B over here.
And now these two are equal.
So this pointer would still remain here itself which is AI.
The AI value does not change, but the j value notice is changing.
The j value has to be decremented by one.
So for depee and I j the insert value would be dp at I j minus one, which actually is the left value
right, so dp at I j minus one.
Again over here this becomes t and nothing because this over here is nothing.
So the subproblem becomes t and nothing and t at and nothing is this cell over here which is the left
value of dp at I j.
So for SL the insert value would be one plus its left value.
Again we have to do one plus because the act of inserting is one operation.
So insertion is the left column for dp at ij which is this column over here.
Now let's take a look at deletion.
Again we are trying to find dp at ij.
So we have T over here and B over here.
And we see that these two are not equal.
So if we delete this t over here we are left with nothing in word one.
And we have b in word two.
And this subproblem is what you have over here right.
Nothing in word one and b in word.
Two.
So that's this cell over here, which is the top cell.
So again this is dp and ij.
Now the cell which is above it.
Or the top cell would give you the value of the delete operation.
And again you'd have to do one plus that because the act of deletion is an operation.
Now what about replace?
Let's take a look at that again.
We are considering T and B and these two are not equal.
So replacing t with B would make it b and b.
And then we would have to move both the pointers.
So we would be comparing nothing and nothing.
This part which is the subproblem left and nothing and nothing is this cell over here which is the diagonal
cell.
Right.
So that's this cell over here for DP at IJ.
And again we would have to do one plus because the act of replacing is an operation.
So we have seen that insertion is the left cell deletion is the top cell and replacing is the diagonal
cell.
And in each of these cases we would have to do one plus.
So the answer is one plus each of these.
And then we would have to find the minimum value of these.
So that means insertion is two.
Deletion is also two.
And replacing has a value of one.
So the minimum value is one.
And therefore we can fill one in this cell over here.
Now let's proceed to the next cell again.
Over here we have T and over here we have E.
And we see that these two are not equal.
So we have to compute insert delete and replace.
So insert is one which is this value.
Over here delete is two which is this value over here.
And replace is also one.
So the minimum among these three is one and one plus one is equal to two.
So we can fill two over here.
Then we proceed to the next cell.
So over here also we see we have T and L.
They are not equal.
So the minimum among these three is two and two plus one is three.
So we can fill three over here.
And we are done with this row.
We proceed to the next cell.
Over here we have E and B and these two are not equal.
So we have to take the minimum of these three values which is one because we have one over here and
one over here.
And one plus one is two.
So we can fill two over here.
And then for this subproblem we have e over here.
And we have e over here as well.
They are equal.
So because they are equal depee at ij will just be DP at I minus one j minus one, which is the diagonal
element.
So this one over here can be filled over here as well.
And then we proceed to the next cell.
We have E and L and they are not equal.
So we take the minimum of these three which is one.
And again one has to be added to that.
So one plus one gives us two which is what we can fill over here.
And we're done with this row.
Now let's proceed to the next row.
So over here we have B and we have b over here as well.
And these two are equal.
So we can just take the diagonal element which is dp at I minus one j minus one.
So this two over here can be filled over here as well.
And then we proceed to the next cell.
We have B and we have e.
They are not equal.
So we take the minimum of these three values which is one.
And we add one to that.
So we get two which is what we fill over here.
Then we come over here again we have b and l.
These are not equal.
So we take the minimum of these three values which is one.
And we add one to it to get the value two.
And we are done with this row as well.
So let's proceed and identify what can be filled.
Over here we have L and we have B.
They are not equal.
So we take the minimum of these three which is two and two plus one is three.
So we can fill three over here.
And then over here.
Also l and E are not equal.
We take the minimum of these three which is two and two plus one is three.
We fill three over here.
And then we have L and L.
They are equal.
So this value is going to be just this value over here.
So we can fill two over here.
And we are done with this row.
And then let's fill this cell.
We have E over here and B over here.
They are not equal.
So we take the minimum of these three which is three.
And three plus one is equal to four.
And we can fill four over here.
And then coming to this cell we have E over here and we have E over here as well.
They are equal.
So we can just take this three and fill it over here.
And then we come to this cell.
We have E over here and L over here.
They are not equal.
So the minimum of these three is two.
And two plus one is equal to three which is what we can fill over here.
And this is the answer to the solution because as we have discussed this cell represents the problem
of converting t b e into bell, which is the original problem which was given to us.
So the answer to this question is three.