Let's now get into the code for solving the edit distance question.
So over here we're going to write the recursive approach for solving this question.
And we would need a helper function.
And let me just call this number of operations okay.
And to this function we will be passing two input parameters.
Let's call it index one and index two.
And we will be using these values or these indices to iterate through word one and word two respectively.
Okay.
And we will be writing the base case over here.
And we will also be writing the recursive case over here okay.
So this is going to be the function that we will be recursively calling.
And finally we will just return what we get when we call this function.
Now again we are going to write this function in a way that it will return the number of operations
that are required.
So that's why whatever we get back from this call, we can just return, okay.
And when we call this function for the first time, I'm going to pass zero and zero.
And again that's because how I'm going to write the recursive solution over here, as we have discussed
many times, you can write recursive solutions either going from zero to the last index, or you can
go from the last index to zero.
Okay.
So over here let's go from zero to the last index of word one and word two respectively.
And therefore when we call this function for the first time I am passing the inputs zero and zero.
All right.
So this is the skeleton of the solution that we are going to write.
Now let's go ahead and write the details.
First let's take a look at the base case.
Now when it comes to the base case there are three possibilities.
The first possibility is that as we go over the characters in word one and word two, let's say that
at a point both index one and index two are invalid or beyond the last valid index.
So that's the first possibility.
Now let me just write placeholders for these scenarios.
So we can say if index one greater than n minus one.
And again we will have to define over here that n is the length of word one.
But let's do that in a minute.
But over here I'm just quickly writing the placeholder.
So if index one is greater than n minus one and index two is greater than n minus one.
So that's the scenario that we just now discussed.
And again quickly let me define n and m over here.
So where n is equal to word one dot length and where n is equal to word two dot length.
All right.
So again this is the first possibility.
Now the next possibility is that only one is out of bound okay.
So over here we are checking whether both are out of bound.
And if this is not true then we are going to check whether only one of the indices is out of bound.
So that would be if let's write one of the cases.
If index one is greater than n minus one okay.
That's a possibility.
And if that is not the case, we will check whether index two is greater than m minus one okay.
So these are the possible base cases.
Now let's discuss what should happen in each of these cases.
Now if both of these indices are out of bound we are actually comparing an empty string with another
empty string.
And for that we would need no operation to make them equal.
Right.
And because of that over here we will just return zero.
But if the case is that only one of the indices is out of bound, then like for example, over here
index one is out of bound.
And in that case, as we have discussed in the previous video, we would have to do still m minus index
two number of operations okay.
So that's what we're going to return over here.
And similarly over here we will be returning n minus index one.
All right.
So we are done with the base cases.
Now let's proceed towards the recursive case.
Now if we were not able to return anything over here and we come to the recursive case, we are first
going to check whether the two characters that we are comparing are equal or not.
So we can say if word one at index one is equal to word two at index two.
So if these two are equal.
So we're going to check that.
And the other possibility is that these two are not equal okay.
So again that would be the case that we come over here.
So these two are not equal.
And in that case we would have to calculate insert and delete.
Okay.
And replace.
All right.
So first let's take a look at the scenario where the two characters that we are comparing are actually
equal.
Now if that is the case then we can just return and we'll call again recursively the same helper function.
And to this we will pass index one plus one and index two plus one.
Or in other words we are moving both the indices one step ahead okay.
All right.
Now that's pretty straightforward.
Now, if this is not the case, then we come over here and we have to calculate, insert, delete and
replace.
And then we would have to return the minimum between these because that's the question right.
We want to identify the minimum number of operations required.
So in this case we would have to calculate insert delete and replace.
And we will return the minimum of these three.
So that's what we're going to do okay.
Now what about these three insert delete and replace.
Now let's go ahead and fill in the details.
As we have discussed in the previous video, if we do a replace operation, then the two characters
that we are comparing become equal.
And therefore we would need to move both the indices.
Therefore, over here replace is equal to one plus what we get back from a recursive call to the same
helper function, and to this we pass index one plus one and index two plus one.
Okay, now what about delete?
If we are comparing two characters and let's say they are not equal and therefore we are deleting the
character in word one.
So we have deleted that character, and therefore we would have to move the index that we are using
to iterate through the characters in word one, which is index one, right?
Therefore, for delete we would have to move index one, but we will not move index two.
So delete op is going to be equal to one plus whatever we get back from the recursive call to number
of operations and to this function, we are going to pass index one plus one.
But index two will remain as it is.
All right.
And in a similar manner when we insert right.
So when we insert two word one the character inserted and the character that we were considering in
word two become equal.
And therefore we would have to move index two, right?
Because index one is still pointing at the character, which was not equal to the character in index
two.
In word two.
And therefore we do not need to move index one, but we have to only move index two.
So insert is equal to one plus whatever we get back from the recursive call to the helper function,
and to this we pass in index one and index two plus one.
All right.
And that's it.
So again over here we find insert delete and replace.
And we return the minimum between these three.
All right.
So that should take care of this 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.
So this is the recursive solution for the edit distance question.