Welcome back.
In this video, let's get started with another coding interview question which is called Edit Distance.
So the question reads given two strings word one and word two, return the minimum number of operations
required to convert word one to word two.
You have the following three operations permitted on a word.
Insert a character.
Delete a character or replace a character.
So this is the question.
Now let's try to first understand this question together.
So over here it says that we will be given two strings.
And the strings are called word one and word two.
And ultimately we would want to convert word one to word two.
And the expected output is the minimum number of operations required to achieve that.
Now let's take a look at an example.
Let's say the word which is given to us is t e b l e.
And let's say we want to convert this word to b e l.
So this would be word one.
And this over here would be word two.
Now for achieving this we could initially convert T to B which would be a replace operation.
So now the word looks like this b e b l e.
Now if we go ahead and delete this b.
And delete this E.
Notice that this word has changed to b e l, which is the second word.
Now for achieving this we have to do one replace operation and two delete operations.
So therefore the expected output would be three.
That is three operations or the minimum number of operations to convert table to bell is three.
Now a quick side note before we go ahead and write a few test cases.
Over here, it was mentioned that we had to convert word one to word two.
But notice that even if the question was to convert word two to word one, the number of operations
needed would still be the same.
Or in other words, the number of operations required to convert.
Table two Bell and bell to table are one and the same, so we would need the same number of operations
for this.
When the allowed operations are replaced delete and insert.
Now why is that.
So we have seen how to convert table to bell with three operations.
Now let's say we start with Bell.
I could convert this to table by changing this b to t.
So this becomes t e l.
And then I could just insert a b over here.
And an E over here.
So it becomes stable.
And again notice I had to do three operations.
So this was a quick side note.
Now let's get back to the question.
Now remember whenever you're presented with a coding interview question, it's very important to ask
any clarifying questions that you may have.
So a possible question that you could ask over here is will there be only lowercase characters, or
would there be also a possibility of being given uppercase characters as well in the two strings that
are given to us?
Now let's say the interviewer replies, no, the strings that would be given to you will only have lowercase
characters.
Another possible question that you could ask is is it possible to be given an empty word as input?
Now let's say the interviewer replies, yes, that's possible.
So let's say word one is empty and word two is a valid word.
Then you would have to return the number of operations required to convert this empty string to word
two.
So we have understood the question and we have also asked clarifying questions.
Now let's proceed and come up with a few test cases for this question.
Now we've already seen an example.
If we were to convert table to Bell we need three operations.
Now if word one is an empty string and word two is a b, then we would have to do two insert operations
to change the empty string to a b.
So initially we could insert a and then we could insert b.
So for this combination the output required is two.
And if we are given two strings that are equal then we would not need any operation to be done and therefore
the required output would be zero.