1
00:00:00,200 --> 00:00:04,520
Let's now get into the code for solving the edit distance question.

2
00:00:04,520 --> 00:00:08,840
So over here we're going to write the recursive approach for solving this question.

3
00:00:08,840 --> 00:00:10,850
And we would need a helper function.

4
00:00:10,850 --> 00:00:15,530
And let me just call this number of operations okay.

5
00:00:17,890 --> 00:00:23,140
And to this function we will be passing two input parameters.

6
00:00:23,140 --> 00:00:26,290
Let's call it index one and index two.

7
00:00:26,290 --> 00:00:34,360
And we will be using these values or these indices to iterate through word one and word two respectively.

8
00:00:34,360 --> 00:00:34,870
Okay.

9
00:00:34,870 --> 00:00:37,420
And we will be writing the base case over here.

10
00:00:39,190 --> 00:00:42,970
And we will also be writing the recursive case over here okay.

11
00:00:42,970 --> 00:00:46,240
So this is going to be the function that we will be recursively calling.

12
00:00:46,240 --> 00:00:51,460
And finally we will just return what we get when we call this function.

13
00:00:51,460 --> 00:00:56,620
Now again we are going to write this function in a way that it will return the number of operations

14
00:00:56,620 --> 00:00:57,400
that are required.

15
00:00:57,400 --> 00:01:01,960
So that's why whatever we get back from this call, we can just return, okay.

16
00:01:01,960 --> 00:01:07,210
And when we call this function for the first time, I'm going to pass zero and zero.

17
00:01:07,210 --> 00:01:12,670
And again that's because how I'm going to write the recursive solution over here, as we have discussed

18
00:01:12,670 --> 00:01:19,330
many times, you can write recursive solutions either going from zero to the last index, or you can

19
00:01:19,330 --> 00:01:21,430
go from the last index to zero.

20
00:01:21,430 --> 00:01:21,760
Okay.

21
00:01:21,760 --> 00:01:28,030
So over here let's go from zero to the last index of word one and word two respectively.

22
00:01:28,030 --> 00:01:34,240
And therefore when we call this function for the first time I am passing the inputs zero and zero.

23
00:01:34,420 --> 00:01:34,930
All right.

24
00:01:34,930 --> 00:01:37,720
So this is the skeleton of the solution that we are going to write.

25
00:01:37,750 --> 00:01:40,330
Now let's go ahead and write the details.

26
00:01:40,330 --> 00:01:42,790
First let's take a look at the base case.

27
00:01:42,790 --> 00:01:46,690
Now when it comes to the base case there are three possibilities.

28
00:01:46,690 --> 00:01:53,530
The first possibility is that as we go over the characters in word one and word two, let's say that

29
00:01:53,530 --> 00:02:01,300
at a point both index one and index two are invalid or beyond the last valid index.

30
00:02:01,300 --> 00:02:02,830
So that's the first possibility.

31
00:02:02,830 --> 00:02:06,190
Now let me just write placeholders for these scenarios.

32
00:02:06,190 --> 00:02:10,690
So we can say if index one greater than n minus one.

33
00:02:10,690 --> 00:02:14,950
And again we will have to define over here that n is the length of word one.

34
00:02:14,950 --> 00:02:16,540
But let's do that in a minute.

35
00:02:16,540 --> 00:02:19,120
But over here I'm just quickly writing the placeholder.

36
00:02:19,120 --> 00:02:26,410
So if index one is greater than n minus one and index two is greater than n minus one.

37
00:02:26,410 --> 00:02:29,140
So that's the scenario that we just now discussed.

38
00:02:29,350 --> 00:02:32,530
And again quickly let me define n and m over here.

39
00:02:32,530 --> 00:02:41,980
So where n is equal to word one dot length and where n is equal to word two dot length.

40
00:02:41,980 --> 00:02:42,430
All right.

41
00:02:42,430 --> 00:02:44,770
So again this is the first possibility.

42
00:02:44,770 --> 00:02:49,600
Now the next possibility is that only one is out of bound okay.

43
00:02:49,600 --> 00:02:52,660
So over here we are checking whether both are out of bound.

44
00:02:52,660 --> 00:02:58,900
And if this is not true then we are going to check whether only one of the indices is out of bound.

45
00:02:58,900 --> 00:03:02,620
So that would be if let's write one of the cases.

46
00:03:02,620 --> 00:03:07,300
If index one is greater than n minus one okay.

47
00:03:07,390 --> 00:03:08,500
That's a possibility.

48
00:03:08,500 --> 00:03:15,730
And if that is not the case, we will check whether index two is greater than m minus one okay.

49
00:03:15,730 --> 00:03:18,160
So these are the possible base cases.

50
00:03:18,160 --> 00:03:22,690
Now let's discuss what should happen in each of these cases.

51
00:03:22,690 --> 00:03:29,920
Now if both of these indices are out of bound we are actually comparing an empty string with another

52
00:03:29,920 --> 00:03:30,670
empty string.

53
00:03:30,670 --> 00:03:34,720
And for that we would need no operation to make them equal.

54
00:03:34,720 --> 00:03:35,170
Right.

55
00:03:35,170 --> 00:03:38,470
And because of that over here we will just return zero.

56
00:03:38,470 --> 00:03:44,800
But if the case is that only one of the indices is out of bound, then like for example, over here

57
00:03:44,800 --> 00:03:46,570
index one is out of bound.

58
00:03:46,570 --> 00:03:53,950
And in that case, as we have discussed in the previous video, we would have to do still m minus index

59
00:03:53,950 --> 00:03:56,230
two number of operations okay.

60
00:03:56,230 --> 00:03:58,030
So that's what we're going to return over here.

61
00:03:58,030 --> 00:04:03,700
And similarly over here we will be returning n minus index one.

62
00:04:03,700 --> 00:04:04,210
All right.

63
00:04:04,210 --> 00:04:06,250
So we are done with the base cases.

64
00:04:06,250 --> 00:04:09,400
Now let's proceed towards the recursive case.

65
00:04:09,640 --> 00:04:16,180
Now if we were not able to return anything over here and we come to the recursive case, we are first

66
00:04:16,180 --> 00:04:21,400
going to check whether the two characters that we are comparing are equal or not.

67
00:04:21,400 --> 00:04:31,600
So we can say if word one at index one is equal to word two at index two.

68
00:04:31,600 --> 00:04:33,640
So if these two are equal.

69
00:04:33,640 --> 00:04:34,990
So we're going to check that.

70
00:04:34,990 --> 00:04:39,310
And the other possibility is that these two are not equal okay.

71
00:04:39,310 --> 00:04:42,700
So again that would be the case that we come over here.

72
00:04:42,700 --> 00:04:44,110
So these two are not equal.

73
00:04:44,110 --> 00:04:49,570
And in that case we would have to calculate insert and delete.

74
00:04:52,530 --> 00:04:53,130
Okay.

75
00:04:53,520 --> 00:04:54,810
And replace.

76
00:04:56,190 --> 00:04:56,700
All right.

77
00:04:56,700 --> 00:05:02,340
So first let's take a look at the scenario where the two characters that we are comparing are actually

78
00:05:02,340 --> 00:05:02,910
equal.

79
00:05:02,940 --> 00:05:09,270
Now if that is the case then we can just return and we'll call again recursively the same helper function.

80
00:05:09,270 --> 00:05:14,640
And to this we will pass index one plus one and index two plus one.

81
00:05:14,640 --> 00:05:20,490
Or in other words we are moving both the indices one step ahead okay.

82
00:05:22,140 --> 00:05:22,800
All right.

83
00:05:22,800 --> 00:05:24,810
Now that's pretty straightforward.

84
00:05:24,840 --> 00:05:31,740
Now, if this is not the case, then we come over here and we have to calculate, insert, delete and

85
00:05:31,740 --> 00:05:32,400
replace.

86
00:05:32,400 --> 00:05:37,470
And then we would have to return the minimum between these because that's the question right.

87
00:05:37,470 --> 00:05:41,160
We want to identify the minimum number of operations required.

88
00:05:41,310 --> 00:05:45,660
So in this case we would have to calculate insert delete and replace.

89
00:05:45,660 --> 00:05:48,720
And we will return the minimum of these three.

90
00:05:48,720 --> 00:05:50,700
So that's what we're going to do okay.

91
00:05:50,700 --> 00:05:54,750
Now what about these three insert delete and replace.

92
00:05:54,750 --> 00:05:57,120
Now let's go ahead and fill in the details.

93
00:05:57,120 --> 00:06:03,570
As we have discussed in the previous video, if we do a replace operation, then the two characters

94
00:06:03,570 --> 00:06:05,610
that we are comparing become equal.

95
00:06:05,610 --> 00:06:08,760
And therefore we would need to move both the indices.

96
00:06:08,760 --> 00:06:16,380
Therefore, over here replace is equal to one plus what we get back from a recursive call to the same

97
00:06:16,380 --> 00:06:22,830
helper function, and to this we pass index one plus one and index two plus one.

98
00:06:22,830 --> 00:06:25,230
Okay, now what about delete?

99
00:06:25,530 --> 00:06:31,350
If we are comparing two characters and let's say they are not equal and therefore we are deleting the

100
00:06:31,350 --> 00:06:32,760
character in word one.

101
00:06:32,760 --> 00:06:38,640
So we have deleted that character, and therefore we would have to move the index that we are using

102
00:06:38,670 --> 00:06:42,660
to iterate through the characters in word one, which is index one, right?

103
00:06:42,660 --> 00:06:47,970
Therefore, for delete we would have to move index one, but we will not move index two.

104
00:06:47,970 --> 00:06:54,330
So delete op is going to be equal to one plus whatever we get back from the recursive call to number

105
00:06:54,330 --> 00:06:59,370
of operations and to this function, we are going to pass index one plus one.

106
00:06:59,370 --> 00:07:02,220
But index two will remain as it is.

107
00:07:02,790 --> 00:07:03,300
All right.

108
00:07:03,300 --> 00:07:07,230
And in a similar manner when we insert right.

109
00:07:07,230 --> 00:07:13,560
So when we insert two word one the character inserted and the character that we were considering in

110
00:07:13,560 --> 00:07:14,820
word two become equal.

111
00:07:14,820 --> 00:07:19,140
And therefore we would have to move index two, right?

112
00:07:19,140 --> 00:07:24,420
Because index one is still pointing at the character, which was not equal to the character in index

113
00:07:24,420 --> 00:07:24,660
two.

114
00:07:24,690 --> 00:07:25,410
In word two.

115
00:07:25,410 --> 00:07:30,540
And therefore we do not need to move index one, but we have to only move index two.

116
00:07:30,570 --> 00:07:37,020
So insert is equal to one plus whatever we get back from the recursive call to the helper function,

117
00:07:37,020 --> 00:07:42,360
and to this we pass in index one and index two plus one.

118
00:07:43,200 --> 00:07:43,710
All right.

119
00:07:43,710 --> 00:07:44,580
And that's it.

120
00:07:44,580 --> 00:07:48,210
So again over here we find insert delete and replace.

121
00:07:48,210 --> 00:07:51,090
And we return the minimum between these three.

122
00:07:51,090 --> 00:07:51,660
All right.

123
00:07:51,660 --> 00:07:53,820
So that should take care of this question.

124
00:07:53,820 --> 00:07:58,230
Now let's go ahead and run this code and see if it's passing all the test cases.

125
00:07:58,860 --> 00:08:00,720
And you can see that it's working.

126
00:08:00,720 --> 00:08:02,610
It's passing all the test cases.

127
00:08:02,610 --> 00:08:06,870
So this is the recursive solution for the edit distance question.