Let's now get into the code and implement the tabulation approach that we have discussed in the previous
videos.
Okay.
So we are given these two words.
We have word one and word two.
And let's say n is equal to the length of word one.
Similarly let's say m is equal to the length of word two.
Now we would also need a 2D array, as we have discussed in the previous video.
And this deep array is going to have n plus one rows and m plus one columns.
So I can say let d p is equal to array dot from and over here we'll have length n plus one because we
want n plus one rows.
And over here I'll say array at n plus one because we want m plus one columns.
And what we will do is over here.
We will just go ahead and fill every cell in this array with the value zero.
All right.
Now let's go ahead and initialize the first row and first column with the values that we need.
So we have discussed in the previous video that for the first row like let's say there are five columns.
So in that case the values that we need in the first row are 012, three, four.
Similarly, if there are let's say five rows, then the values that we would need in the first column
are zero, one two, three, four okay.
So let's go ahead and implement that.
So I can say for let I is equal to zero I less than n or less than equal to n I plus plus okay.
Because we have n plus one rows.
And then let me say d p at I zero okay is equal to I.
Now over here we are keeping the column value the same.
And we are changing the row values okay.
So this over here helps us initialize the values for the first column.
Now let's do the same thing for the first row.
So let me say for let j is equal to zero j less than or equal to m because we have m plus one columns
okay.
And we have j plus plus and over here and say depee at zero j is equal to j.
Okay.
So this helps us initialize the values in the first row.
Now that we are done with this, let's go ahead and iterate over the remaining cells in the DP table.
And for that we will use a nested for loop.
So I'll say for let I is equal to one I less than or equal to n I plus plus.
And then we can say for let j is equal to one j less than or equal to m j plus plus.
Okay.
And again what we are going to do is we're going to check whether the characters that we are comparing
in word one and word two are equal.
And if they are equal then we do not need any operation.
So we can just say dp at I j in that case would be dp at I minus one, j minus one.
Okay.
So let's first implement that.
And if that is not the case like if the characters are not equal we proceed and calculate replace delete
and insert.
And we assign the minimum among these three to dp at I j.
So I can say if word one dot char.
Hat I minus one okay.
If this is equal to word two dot chart j minus one.
So if these two characters are equal then we can just say dp at I, j is equal to dp at I minus one
j minus one.
All right.
Now again remember over here we have I minus one and j minus one.
Because the words which are given to us they are zero indexed okay.
So to convert the respective value of I and j which we are getting from the DP table in terms of a zero
indexed value, which is the case for word one and word two, we have to subtract one okay.
So that's why we are doing I minus one and J minus one over here.
Now if this is not the case that is if these two characters are not equal then we'll have to go ahead
and find replace.
And we'll also have to find delete.
Okay.
And we will also have to find insert.
And finally we'll just say dp at ij is equal to math dot min.
And then we'll have these three values over here replace delete op and insert.
Okay.
So replace would be one plus.
And again we have one plus in all of these three cases because it's one operation right.
So that's why we have one plus.
And in the case of replace we have seen that we have to move both the indices.
So we would have DP at I minus one J minus one over here.
Now in the case of delete we have seen that we only have to move the first index.
So we will have DP at I minus one and j over here.
And in the case of insert we will have to only move index two.
So this would be DP at I and you have j minus one.
All right that's it.
So this will help us to fill the DP array.
And once we are out of this for loop we will just have to return DP at n m which is the last cell in
the DP array.
So this should take care of it.
Now let's go ahead and run this code and see if it's passing all the test cases.
All right.
So there's an error.
So I have made a typo over here.
Okay.
So let's correct that and let's again run it.
And you can see that it's working.
It's passing all the test cases.
So this is the tabulation approach for solving the edit distance question.