Welcome back.
Let's now discuss how to solve the edit distance question.
Now we will not directly start with the bottom up or tabulation approach, but rather first we will
write the recursive solution for this question.
Then we will memorize it by just adding a few lines of code.
And once we are done with these two steps, we will proceed and take a look at the tabulation or bottom
up approach for solving the edit distance question, and then come up with the space optimized bottom
up approach.
So let's get started with the recursive approach for solving this question.
Now, because we are thinking of a recursive approach, we will have to think of the base case and the
recursive case, because we'll be writing a recursive function and we will be recursively calling it
inside the body of the function.
So first let's think of what choices are available when we try to convert word one to word two.
Now now for this let's make use of a choice diagram.
And let's consider two possibilities.
So let's say in one case we are going from zero to n.
Remember whenever we write recursive solutions you can either go from zero to n or n to zero.
So you can do it in both ways.
Over here let's think of the zero to n approach.
So let's say you're comparing the zeroth character in A, B, C and a PC.
So this is word one and this is word two.
And you're trying to convert this word to this word over here.
And let's say we are comparing the characters at index zero in these two strings over here.
So we see that they are equal.
And if the characters are equal, then we do not need to do any operations to convert this to this because
they are already equal and therefore we can just move ahead and the remaining subproblem becomes this
part over here and this part over here.
So this is one case where we see that the characters that we are comparing are equal.
Now on the other side, if the characters that we are comparing are not equal, what would be the choices
that we have.
So over here again we are comparing the characters at the indices zero and zero.
And we see that we have T over here and we have B over here.
And they are not equal.
Now the question says that we have three possible operations that can be done.
So the possible operations are insertion deletion and replacing characters.
So let's go ahead and write these two strings for these three scenarios.
To analyze what would be happening when we do these three operations respectively.
So over here we have insertion.
And again what is the case.
We are comparing T and B.
And we have seen that these two are not equal.
And we are going from zero to n.
Now if this is the case inserting a character would mean adding a b over here so that this b and this
b are now equal.
Now notice that initially the pointers were over here.
And over here.
And we saw that T and B are not equal.
And we inserted a b over here.
And therefore this pointer can still stay over here itself.
But because we know that these two are now equal we would have to move this ahead.
So the pointers now would be over here and over here.
So that means that the pointer which was used for iterating over the characters for word two would have
to be moved in this case to identify the remaining subproblems.
Now what about deletion again?
What's the scenario?
We are comparing the characters over here and over here.
And we see that these two are not equal.
And we want to convert word one to word two.
Now, because these two are not equal, deletion would mean that we are deleting this character over
here.
So this would be deleted.
And because this is deleted, we would have to move this pointer ahead to come to the next character
over here.
So notice that we would have to move the pointer used to iterate over the characters of word one.
And this pointer stays where it was initially itself.
So this is how we can identify the subproblem when we do the deletion operation.
Now what about replacing characters?
Again the scenario is that we are comparing these two characters.
We see that they are not equal and we want to convert word one to word two.
Now, replacing this character would mean that instead of T over here we would write B.
Now we know that these two are equal, and because these two are equal, we would have to move both
the pointers.
Because initially this pointer was pointing over here and this pointer was pointing to this character.
Now we know that these two are equal.
And therefore we would have to move both the pointers or both the variables used to iterate over the
indices of word one and word two.
So this over here helps us understand how to identify the subproblem in case of insertion, deletion
and replacing characters.
So to solve this question, we would just have to write a recursive function which takes two values
as inputs.
And we will use those two values as pointers to characters in word one and word two.
And then we will compare characters.
If we see that they are equal, then we would just proceed with the remaining subproblem.
And if we see that they are not equal, we would calculate three versions of making word one to word
two.
So we would say insertion is equal to one plus.
And then we would recursively call the same function.
And we would pass the indices as we have discussed over here to the function.
And we would say deletion is equal to one plus.
Again we would call the recursive function again.
And we would pass these indices over here.
And we would say replace is equal to one plus.
And then again we would recursively call the same function and increment both the pointers as we have
discussed over here.
And then these three would give us three respective values.
And the answer would be the minimum of these three, because the question asks us to identify the minimum
number of operations required to change word one to word two.
So we have discussed the recursive case for the recursive solution for the edit distance question.
And now let's also proceed and discuss the base condition for this approach.
Now to understand and discuss the base condition, let's take three examples.
And again we could write the solution either going from zero to n or n to zero.
And the base case will vary based on which approach we take.
But over here for our discussion we are going from zero to n.
So let's think of these three examples.
So let's say in one case we are given a, b, C and Pqr the second example is a b c and p q r s t,
and the third example is a b c d e f and p q r.
Now in this example, let's say that we have reached over here for word one, and we have reached over
here for word two because we were using two pointers to iterate over these characters.
So again this scenario indicates that there's nothing left in word one and nothing left in word two.
And if this is the base case that we encounter, then we can just return zero.
Because to change an empty string to an empty string, we don't need any operations.
Now, what about this case over here?
This would mean that we have reached over here with the pointer that was used to iterate over the characters
for word one, and we have reached over here with the pointer that was used to iterate over the characters
for word two.
So this subproblem over here would mean that we would need to convert an empty string to s t.
So for this we would need two insert operations, or we would need to insert s and t.
And therefore if this is the base case that we encounter, we should return two.
Now what about this case over here.
This case over here would indicate that the pointer which was used to iterate over the characters for
word one is over here.
And the pointer, which was used to iterate over the characters for word two is over here.
So the subproblem at hand is to convert d, e, f to an empty string, and for this we would need three
operations or three delete operations.
So in this case we would have to return three.
So these are the three possible base cases that we could encounter based on the length of the input
strings word one and word two.
So over here if both the pointers become out of bound or greater than the last valid indices respectively,
we can return zero.
And if only one of them becomes greater than the last valid index and there are still characters left
in the other word, then we would have to return the number of characters that are left in the other
word.
So notice over here we are returning two and over here we are returning three.