1
00:00:00,970 --> 00:00:02,590
Hey there and welcome back!

2
00:00:02,590 --> 00:00:09,730
So far we have discussed the recursive approach and the memoization approach for solving the edit distance

3
00:00:09,730 --> 00:00:10,330
question.

4
00:00:10,330 --> 00:00:17,140
Now for the memoization approach, we have seen that the space and time complexity are of the order

5
00:00:17,140 --> 00:00:18,460
of n into m.

6
00:00:18,460 --> 00:00:23,230
And of course the memoization approach is a recursive approach.

7
00:00:23,230 --> 00:00:30,220
Now let's get started with the bottom up or tabulation approach, which is an iterative approach for

8
00:00:30,220 --> 00:00:32,020
solving the edit distance question.

9
00:00:32,350 --> 00:00:37,300
To discuss the tabulation approach, let's take an example.

10
00:00:37,300 --> 00:00:41,770
Let's say word one is table and word two is bill.

11
00:00:41,770 --> 00:00:44,740
So we need to convert table to bill.

12
00:00:44,740 --> 00:00:51,010
Now we will need a DP table of size six into four.

13
00:00:51,010 --> 00:00:55,480
So the length of table is five and the length of bill is three.

14
00:00:55,510 --> 00:01:00,130
Now if we were to add one to each we get six and four.

15
00:01:00,130 --> 00:01:04,060
And this would be the size of the DP table that we need.

16
00:01:04,060 --> 00:01:10,180
Now, as we discussed previously, this is a common approach when it comes to the bottom up or tabulation

17
00:01:10,180 --> 00:01:13,000
approach to have an extra row and column.

18
00:01:13,000 --> 00:01:19,660
So in this case also we would have columns for Bill and we have an extra column.

19
00:01:19,660 --> 00:01:22,420
And we have rows for t e b l e.

20
00:01:22,510 --> 00:01:24,700
And we have an extra row.

21
00:01:24,700 --> 00:01:28,060
Now what would a cell over here mean.

22
00:01:28,060 --> 00:01:38,380
So for example this cell over here is the subproblem where we have to convert T into B because this

23
00:01:38,380 --> 00:01:41,770
is the last row over here and this is the last column.

24
00:01:41,770 --> 00:01:44,530
So we would have to convert T to B.

25
00:01:44,530 --> 00:01:50,020
And the number of operations required for that would be the value that we fill over here.

26
00:01:50,620 --> 00:01:58,870
On a similar note, this cell over here would represent the subproblem of converting t e b l e into

27
00:01:58,870 --> 00:01:59,830
just b.

28
00:02:00,370 --> 00:02:07,630
Now that we have come up with the DP table required, let's also fill in the initial conditions in this

29
00:02:07,630 --> 00:02:08,170
table.

30
00:02:08,170 --> 00:02:14,020
So the initial conditions would be this row over here and this column over here.

31
00:02:14,050 --> 00:02:22,030
Now notice that for example, this problem or this cell would represent converting an empty string into

32
00:02:22,030 --> 00:02:27,430
the string B which would take one operation because we have to insert B to the empty string.

33
00:02:27,430 --> 00:02:27,820
Right.

34
00:02:27,820 --> 00:02:34,750
So in this manner over here notice that the initial values would be zero, one, two and three.

35
00:02:34,750 --> 00:02:40,660
Because again over here we just have to convert an empty string to an empty string which requires zero

36
00:02:40,660 --> 00:02:41,380
operations.

37
00:02:41,380 --> 00:02:48,880
But over here we would have to convert an empty string to Belle which requires three insertion operations.

38
00:02:48,880 --> 00:02:52,960
So these are the initial values that we can fill over here.

39
00:02:52,960 --> 00:03:00,220
Now when it comes to the first column over here, the initial values are going to be 012, three, four

40
00:03:00,220 --> 00:03:00,940
and five.

41
00:03:00,940 --> 00:03:09,610
Because for example this problem this problem would mean converting t b l into an empty string which

42
00:03:09,610 --> 00:03:12,400
requires four deletion operations.

43
00:03:12,400 --> 00:03:14,770
So that's why we need four operations over here.

44
00:03:14,770 --> 00:03:18,820
And in a similar manner here we would need two operations etc..

45
00:03:18,820 --> 00:03:22,210
So we are done with filling the initial conditions.

46
00:03:22,210 --> 00:03:25,510
And we have also come up with the DP table required.

47
00:03:25,510 --> 00:03:32,500
Let's now proceed and iterate through these cells over here to get the final answer over here.

48
00:03:32,500 --> 00:03:41,710
Because notice that this cell represents the problem of converting t e b l e into b e l, which is the

49
00:03:41,710 --> 00:03:42,940
original problem.

50
00:03:43,240 --> 00:03:44,680
So let's get started.

51
00:03:44,680 --> 00:03:51,850
Now whenever we are comparing two characters in word one and word two respectively, as we have seen

52
00:03:51,850 --> 00:03:54,640
previously, there are two possibilities.

53
00:03:54,640 --> 00:04:00,910
One possibility is that the two characters are equal, and the other possibility is that the two characters

54
00:04:00,910 --> 00:04:02,380
are not equal.

55
00:04:02,380 --> 00:04:07,600
Now, if the two characters are equal, we do not need to do any operation.

56
00:04:07,600 --> 00:04:15,730
So depee and IJ, when the two characters are equal, will just be equal to dp at I minus one, j minus

57
00:04:15,730 --> 00:04:16,030
one.

58
00:04:16,030 --> 00:04:19,960
So again for example, over here we see that we have e and e.

59
00:04:20,200 --> 00:04:23,620
So when we are trying t e and b e.

60
00:04:23,800 --> 00:04:32,140
So let me write that over here we are comparing e and e and we have t e and b e as the subproblem,

61
00:04:32,140 --> 00:04:34,600
because that is what is represented by the cell.

62
00:04:34,600 --> 00:04:36,970
And we see that these two are equal.

63
00:04:36,970 --> 00:04:41,530
So we just need to consider these two or the remaining characters.

64
00:04:41,530 --> 00:04:41,920
Right.

65
00:04:41,920 --> 00:04:47,410
So we are reducing one character from word two which is j minus one.

66
00:04:47,410 --> 00:04:50,200
So that's why we have j minus one over here.

67
00:04:50,200 --> 00:04:56,200
And over here also we are reducing one character because of which we are doing I minus one.

68
00:04:56,200 --> 00:05:05,230
So if the characters are equal depee at I j will just be equal to dp at I minus one, j minus one,

69
00:05:05,230 --> 00:05:09,580
which is the diagonal element in the table visually.

70
00:05:09,670 --> 00:05:17,050
Now, if the characters are not equal, then as we have discussed when we thought about the recursive

71
00:05:17,050 --> 00:05:18,550
and memoization approach.

72
00:05:18,550 --> 00:05:24,670
So if the characters are not equal, we have three options insert, delete, and replace.

73
00:05:24,670 --> 00:05:31,990
So we need to identify the number of operations required to solve the subproblem if we are doing insertion,

74
00:05:31,990 --> 00:05:35,320
if you're doing deletion and if you are replacing a character.

75
00:05:35,320 --> 00:05:38,380
So we would have to compute these three separately.

76
00:05:38,380 --> 00:05:43,630
And then depee at ij would be the minimum value among these three.

77
00:05:43,630 --> 00:05:48,790
So again let's take a look at how to identify this from the DP table over here.

78
00:05:48,790 --> 00:05:54,100
So we have insert we have delete and we have replace three possibilities.

79
00:05:54,100 --> 00:05:57,820
Now a quick side note before we go ahead and compute this.

80
00:05:57,820 --> 00:06:06,220
Now let's say we are trying to solve this subproblem over here which is t e b and b e.

81
00:06:08,200 --> 00:06:14,800
Now, the point that I want to convey is that when we see that these two are not equal, let's say we

82
00:06:14,800 --> 00:06:16,660
are trying to insert something.

83
00:06:16,660 --> 00:06:18,430
So we insert E over here.

84
00:06:18,610 --> 00:06:22,390
So we insert E on this side, not on this side.

85
00:06:22,390 --> 00:06:27,910
As we previously discussed when we were discussing the zero to n recursive approach.

86
00:06:27,910 --> 00:06:34,960
Because in the case of tabulation, we are going from the smallest possible subproblem till we reach

87
00:06:34,960 --> 00:06:36,670
the original problem at hand.

88
00:06:36,670 --> 00:06:42,280
So in this case over here for this cell the problem was t e b and b e.

89
00:06:42,640 --> 00:06:45,910
So whenever we are inserting we are inserting over here.

90
00:06:45,910 --> 00:06:48,460
And if we are deleting we are deleting over here.

91
00:06:48,460 --> 00:06:51,370
If we are replacing we are changing this character to E.

92
00:06:51,370 --> 00:06:52,900
So that was a quick side note.

93
00:06:52,900 --> 00:06:58,450
Now let's go ahead and take a look at insert, delete and replace for the case where we are dealing

94
00:06:58,450 --> 00:07:02,500
with this cell where the subproblem is t and b.

95
00:07:03,370 --> 00:07:07,030
So we have t and b and we see that they are not equal.

96
00:07:07,030 --> 00:07:07,690
So.

97
00:07:07,690 --> 00:07:11,590
So when we are trying to insert we would insert B over here.

98
00:07:13,970 --> 00:07:16,310
And now these two are equal.

99
00:07:16,520 --> 00:07:22,010
So this pointer would still remain here itself which is AI.

100
00:07:22,010 --> 00:07:27,650
The AI value does not change, but the j value notice is changing.

101
00:07:28,190 --> 00:07:31,280
The j value has to be decremented by one.

102
00:07:31,280 --> 00:07:42,560
So for depee and I j the insert value would be dp at I j minus one, which actually is the left value

103
00:07:42,560 --> 00:07:44,720
right, so dp at I j minus one.

104
00:07:44,720 --> 00:07:49,460
Again over here this becomes t and nothing because this over here is nothing.

105
00:07:49,460 --> 00:07:58,820
So the subproblem becomes t and nothing and t at and nothing is this cell over here which is the left

106
00:07:58,820 --> 00:08:00,950
value of dp at I j.

107
00:08:01,220 --> 00:08:07,400
So for SL the insert value would be one plus its left value.

108
00:08:07,400 --> 00:08:11,900
Again we have to do one plus because the act of inserting is one operation.

109
00:08:11,900 --> 00:08:17,780
So insertion is the left column for dp at ij which is this column over here.

110
00:08:18,020 --> 00:08:20,210
Now let's take a look at deletion.

111
00:08:20,360 --> 00:08:23,180
Again we are trying to find dp at ij.

112
00:08:23,210 --> 00:08:25,670
So we have T over here and B over here.

113
00:08:25,670 --> 00:08:28,340
And we see that these two are not equal.

114
00:08:28,340 --> 00:08:33,440
So if we delete this t over here we are left with nothing in word one.

115
00:08:33,440 --> 00:08:35,690
And we have b in word two.

116
00:08:35,690 --> 00:08:40,550
And this subproblem is what you have over here right.

117
00:08:40,550 --> 00:08:43,220
Nothing in word one and b in word.

118
00:08:44,050 --> 00:08:44,740
Two.

119
00:08:44,770 --> 00:08:48,490
So that's this cell over here, which is the top cell.

120
00:08:48,850 --> 00:08:50,860
So again this is dp and ij.

121
00:08:50,890 --> 00:08:53,290
Now the cell which is above it.

122
00:08:53,290 --> 00:08:58,120
Or the top cell would give you the value of the delete operation.

123
00:08:58,120 --> 00:09:03,760
And again you'd have to do one plus that because the act of deletion is an operation.

124
00:09:04,370 --> 00:09:06,860
Now what about replace?

125
00:09:07,250 --> 00:09:08,930
Let's take a look at that again.

126
00:09:08,930 --> 00:09:12,410
We are considering T and B and these two are not equal.

127
00:09:12,410 --> 00:09:16,580
So replacing t with B would make it b and b.

128
00:09:16,580 --> 00:09:19,040
And then we would have to move both the pointers.

129
00:09:19,040 --> 00:09:22,190
So we would be comparing nothing and nothing.

130
00:09:22,550 --> 00:09:28,910
This part which is the subproblem left and nothing and nothing is this cell over here which is the diagonal

131
00:09:28,910 --> 00:09:29,330
cell.

132
00:09:30,050 --> 00:09:30,530
Right.

133
00:09:30,530 --> 00:09:33,620
So that's this cell over here for DP at IJ.

134
00:09:33,860 --> 00:09:40,190
And again we would have to do one plus because the act of replacing is an operation.

135
00:09:40,190 --> 00:09:47,780
So we have seen that insertion is the left cell deletion is the top cell and replacing is the diagonal

136
00:09:47,780 --> 00:09:48,230
cell.

137
00:09:48,230 --> 00:09:51,740
And in each of these cases we would have to do one plus.

138
00:09:51,740 --> 00:09:55,430
So the answer is one plus each of these.

139
00:09:55,430 --> 00:09:57,710
And then we would have to find the minimum value of these.

140
00:09:57,710 --> 00:10:00,320
So that means insertion is two.

141
00:10:00,320 --> 00:10:01,850
Deletion is also two.

142
00:10:01,850 --> 00:10:04,250
And replacing has a value of one.

143
00:10:04,250 --> 00:10:06,320
So the minimum value is one.

144
00:10:06,320 --> 00:10:09,950
And therefore we can fill one in this cell over here.

145
00:10:09,950 --> 00:10:13,460
Now let's proceed to the next cell again.

146
00:10:13,460 --> 00:10:16,640
Over here we have T and over here we have E.

147
00:10:16,640 --> 00:10:19,220
And we see that these two are not equal.

148
00:10:19,220 --> 00:10:23,090
So we have to compute insert delete and replace.

149
00:10:23,090 --> 00:10:25,220
So insert is one which is this value.

150
00:10:25,220 --> 00:10:29,150
Over here delete is two which is this value over here.

151
00:10:29,150 --> 00:10:31,040
And replace is also one.

152
00:10:31,040 --> 00:10:35,210
So the minimum among these three is one and one plus one is equal to two.

153
00:10:35,240 --> 00:10:37,070
So we can fill two over here.

154
00:10:37,890 --> 00:10:40,260
Then we proceed to the next cell.

155
00:10:40,260 --> 00:10:43,080
So over here also we see we have T and L.

156
00:10:43,080 --> 00:10:44,460
They are not equal.

157
00:10:44,460 --> 00:10:47,970
So the minimum among these three is two and two plus one is three.

158
00:10:47,970 --> 00:10:49,440
So we can fill three over here.

159
00:10:49,440 --> 00:10:51,600
And we are done with this row.

160
00:10:51,630 --> 00:10:53,460
We proceed to the next cell.

161
00:10:53,460 --> 00:10:57,480
Over here we have E and B and these two are not equal.

162
00:10:57,480 --> 00:11:03,240
So we have to take the minimum of these three values which is one because we have one over here and

163
00:11:03,240 --> 00:11:03,990
one over here.

164
00:11:03,990 --> 00:11:05,460
And one plus one is two.

165
00:11:05,460 --> 00:11:06,900
So we can fill two over here.

166
00:11:06,900 --> 00:11:11,130
And then for this subproblem we have e over here.

167
00:11:11,130 --> 00:11:13,470
And we have e over here as well.

168
00:11:13,620 --> 00:11:14,580
They are equal.

169
00:11:14,580 --> 00:11:22,260
So because they are equal depee at ij will just be DP at I minus one j minus one, which is the diagonal

170
00:11:22,260 --> 00:11:22,710
element.

171
00:11:22,710 --> 00:11:26,040
So this one over here can be filled over here as well.

172
00:11:26,160 --> 00:11:28,590
And then we proceed to the next cell.

173
00:11:28,590 --> 00:11:31,980
We have E and L and they are not equal.

174
00:11:31,980 --> 00:11:35,160
So we take the minimum of these three which is one.

175
00:11:35,160 --> 00:11:37,620
And again one has to be added to that.

176
00:11:37,620 --> 00:11:41,400
So one plus one gives us two which is what we can fill over here.

177
00:11:41,400 --> 00:11:42,930
And we're done with this row.

178
00:11:42,930 --> 00:11:45,420
Now let's proceed to the next row.

179
00:11:45,420 --> 00:11:49,560
So over here we have B and we have b over here as well.

180
00:11:49,560 --> 00:11:51,570
And these two are equal.

181
00:11:51,570 --> 00:11:56,610
So we can just take the diagonal element which is dp at I minus one j minus one.

182
00:11:56,610 --> 00:11:59,880
So this two over here can be filled over here as well.

183
00:11:59,970 --> 00:12:02,400
And then we proceed to the next cell.

184
00:12:02,400 --> 00:12:04,170
We have B and we have e.

185
00:12:04,200 --> 00:12:05,670
They are not equal.

186
00:12:05,670 --> 00:12:09,180
So we take the minimum of these three values which is one.

187
00:12:09,180 --> 00:12:10,770
And we add one to that.

188
00:12:10,770 --> 00:12:13,680
So we get two which is what we fill over here.

189
00:12:14,160 --> 00:12:16,890
Then we come over here again we have b and l.

190
00:12:16,920 --> 00:12:18,210
These are not equal.

191
00:12:18,210 --> 00:12:21,150
So we take the minimum of these three values which is one.

192
00:12:21,150 --> 00:12:24,180
And we add one to it to get the value two.

193
00:12:24,180 --> 00:12:26,160
And we are done with this row as well.

194
00:12:26,160 --> 00:12:29,490
So let's proceed and identify what can be filled.

195
00:12:29,490 --> 00:12:32,820
Over here we have L and we have B.

196
00:12:32,820 --> 00:12:34,050
They are not equal.

197
00:12:34,050 --> 00:12:38,070
So we take the minimum of these three which is two and two plus one is three.

198
00:12:38,070 --> 00:12:39,690
So we can fill three over here.

199
00:12:39,690 --> 00:12:40,800
And then over here.

200
00:12:40,800 --> 00:12:42,900
Also l and E are not equal.

201
00:12:42,900 --> 00:12:46,590
We take the minimum of these three which is two and two plus one is three.

202
00:12:46,590 --> 00:12:47,760
We fill three over here.

203
00:12:47,760 --> 00:12:49,830
And then we have L and L.

204
00:12:49,830 --> 00:12:50,820
They are equal.

205
00:12:50,820 --> 00:12:54,210
So this value is going to be just this value over here.

206
00:12:54,210 --> 00:12:56,160
So we can fill two over here.

207
00:12:56,250 --> 00:12:58,560
And we are done with this row.

208
00:12:58,560 --> 00:13:00,150
And then let's fill this cell.

209
00:13:00,150 --> 00:13:02,250
We have E over here and B over here.

210
00:13:02,250 --> 00:13:03,510
They are not equal.

211
00:13:03,510 --> 00:13:06,120
So we take the minimum of these three which is three.

212
00:13:06,120 --> 00:13:07,980
And three plus one is equal to four.

213
00:13:07,980 --> 00:13:09,480
And we can fill four over here.

214
00:13:09,750 --> 00:13:14,850
And then coming to this cell we have E over here and we have E over here as well.

215
00:13:14,850 --> 00:13:15,750
They are equal.

216
00:13:15,750 --> 00:13:19,080
So we can just take this three and fill it over here.

217
00:13:19,730 --> 00:13:21,320
And then we come to this cell.

218
00:13:21,320 --> 00:13:23,720
We have E over here and L over here.

219
00:13:23,720 --> 00:13:24,890
They are not equal.

220
00:13:24,890 --> 00:13:27,230
So the minimum of these three is two.

221
00:13:27,230 --> 00:13:31,550
And two plus one is equal to three which is what we can fill over here.

222
00:13:31,550 --> 00:13:38,270
And this is the answer to the solution because as we have discussed this cell represents the problem

223
00:13:38,270 --> 00:13:44,900
of converting t b e into bell, which is the original problem which was given to us.

224
00:13:44,900 --> 00:13:47,510
So the answer to this question is three.