1
00:00:00,770 --> 00:00:01,940
Welcome back.

2
00:00:02,180 --> 00:00:08,930
In this video, let's get started with another coding interview question which is called Edit Distance.

3
00:00:09,380 --> 00:00:18,350
So the question reads given two strings word one and word two, return the minimum number of operations

4
00:00:18,350 --> 00:00:22,520
required to convert word one to word two.

5
00:00:23,000 --> 00:00:27,110
You have the following three operations permitted on a word.

6
00:00:27,140 --> 00:00:28,760
Insert a character.

7
00:00:28,790 --> 00:00:32,420
Delete a character or replace a character.

8
00:00:32,570 --> 00:00:34,130
So this is the question.

9
00:00:34,130 --> 00:00:37,550
Now let's try to first understand this question together.

10
00:00:37,580 --> 00:00:41,870
So over here it says that we will be given two strings.

11
00:00:41,870 --> 00:00:46,160
And the strings are called word one and word two.

12
00:00:46,160 --> 00:00:51,140
And ultimately we would want to convert word one to word two.

13
00:00:51,140 --> 00:00:58,520
And the expected output is the minimum number of operations required to achieve that.

14
00:00:58,550 --> 00:01:00,680
Now let's take a look at an example.

15
00:01:00,680 --> 00:01:05,030
Let's say the word which is given to us is t e b l e.

16
00:01:05,390 --> 00:01:09,200
And let's say we want to convert this word to b e l.

17
00:01:09,200 --> 00:01:10,970
So this would be word one.

18
00:01:10,970 --> 00:01:13,790
And this over here would be word two.

19
00:01:13,850 --> 00:01:22,550
Now for achieving this we could initially convert T to B which would be a replace operation.

20
00:01:22,910 --> 00:01:26,540
So now the word looks like this b e b l e.

21
00:01:27,170 --> 00:01:30,080
Now if we go ahead and delete this b.

22
00:01:30,880 --> 00:01:32,800
And delete this E.

23
00:01:33,430 --> 00:01:40,390
Notice that this word has changed to b e l, which is the second word.

24
00:01:40,510 --> 00:01:47,380
Now for achieving this we have to do one replace operation and two delete operations.

25
00:01:47,380 --> 00:01:51,310
So therefore the expected output would be three.

26
00:01:51,310 --> 00:01:58,450
That is three operations or the minimum number of operations to convert table to bell is three.

27
00:01:58,750 --> 00:02:03,850
Now a quick side note before we go ahead and write a few test cases.

28
00:02:04,480 --> 00:02:09,520
Over here, it was mentioned that we had to convert word one to word two.

29
00:02:09,520 --> 00:02:16,990
But notice that even if the question was to convert word two to word one, the number of operations

30
00:02:16,990 --> 00:02:19,360
needed would still be the same.

31
00:02:19,360 --> 00:02:24,070
Or in other words, the number of operations required to convert.

32
00:02:24,070 --> 00:02:31,570
Table two Bell and bell to table are one and the same, so we would need the same number of operations

33
00:02:31,570 --> 00:02:32,350
for this.

34
00:02:32,350 --> 00:02:36,550
When the allowed operations are replaced delete and insert.

35
00:02:36,550 --> 00:02:37,510
Now why is that.

36
00:02:37,510 --> 00:02:41,920
So we have seen how to convert table to bell with three operations.

37
00:02:41,920 --> 00:02:43,990
Now let's say we start with Bell.

38
00:02:46,030 --> 00:02:51,070
I could convert this to table by changing this b to t.

39
00:02:51,130 --> 00:02:54,370
So this becomes t e l.

40
00:02:54,370 --> 00:02:57,490
And then I could just insert a b over here.

41
00:02:58,110 --> 00:03:00,060
And an E over here.

42
00:03:00,060 --> 00:03:01,860
So it becomes stable.

43
00:03:01,860 --> 00:03:05,400
And again notice I had to do three operations.

44
00:03:05,400 --> 00:03:07,230
So this was a quick side note.

45
00:03:07,260 --> 00:03:09,420
Now let's get back to the question.

46
00:03:09,420 --> 00:03:16,080
Now remember whenever you're presented with a coding interview question, it's very important to ask

47
00:03:16,080 --> 00:03:18,510
any clarifying questions that you may have.

48
00:03:18,510 --> 00:03:25,620
So a possible question that you could ask over here is will there be only lowercase characters, or

49
00:03:25,620 --> 00:03:32,550
would there be also a possibility of being given uppercase characters as well in the two strings that

50
00:03:32,550 --> 00:03:33,480
are given to us?

51
00:03:34,050 --> 00:03:41,010
Now let's say the interviewer replies, no, the strings that would be given to you will only have lowercase

52
00:03:41,010 --> 00:03:41,850
characters.

53
00:03:42,300 --> 00:03:49,800
Another possible question that you could ask is is it possible to be given an empty word as input?

54
00:03:49,800 --> 00:03:53,160
Now let's say the interviewer replies, yes, that's possible.

55
00:03:53,160 --> 00:03:59,520
So let's say word one is empty and word two is a valid word.

56
00:03:59,520 --> 00:04:07,110
Then you would have to return the number of operations required to convert this empty string to word

57
00:04:07,140 --> 00:04:07,500
two.

58
00:04:07,500 --> 00:04:12,300
So we have understood the question and we have also asked clarifying questions.

59
00:04:12,570 --> 00:04:17,760
Now let's proceed and come up with a few test cases for this question.

60
00:04:18,000 --> 00:04:20,940
Now we've already seen an example.

61
00:04:20,940 --> 00:04:25,500
If we were to convert table to Bell we need three operations.

62
00:04:25,500 --> 00:04:33,450
Now if word one is an empty string and word two is a b, then we would have to do two insert operations

63
00:04:33,450 --> 00:04:35,670
to change the empty string to a b.

64
00:04:35,670 --> 00:04:39,840
So initially we could insert a and then we could insert b.

65
00:04:39,840 --> 00:04:44,580
So for this combination the output required is two.

66
00:04:44,580 --> 00:04:51,810
And if we are given two strings that are equal then we would not need any operation to be done and therefore

67
00:04:51,810 --> 00:04:54,210
the required output would be zero.