1
00:00:00,110 --> 00:00:06,230
Let's now get into the code and implement the tabulation approach that we have discussed in the previous

2
00:00:06,230 --> 00:00:06,980
videos.

3
00:00:07,070 --> 00:00:07,430
Okay.

4
00:00:07,430 --> 00:00:09,380
So we are given these two words.

5
00:00:09,380 --> 00:00:11,270
We have word one and word two.

6
00:00:11,270 --> 00:00:15,620
And let's say n is equal to the length of word one.

7
00:00:16,250 --> 00:00:19,790
Similarly let's say m is equal to the length of word two.

8
00:00:20,630 --> 00:00:25,460
Now we would also need a 2D array, as we have discussed in the previous video.

9
00:00:25,460 --> 00:00:32,060
And this deep array is going to have n plus one rows and m plus one columns.

10
00:00:32,060 --> 00:00:39,710
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

11
00:00:39,710 --> 00:00:41,300
want n plus one rows.

12
00:00:41,300 --> 00:00:47,480
And over here I'll say array at n plus one because we want m plus one columns.

13
00:00:47,480 --> 00:00:49,190
And what we will do is over here.

14
00:00:49,190 --> 00:00:54,080
We will just go ahead and fill every cell in this array with the value zero.

15
00:00:55,160 --> 00:00:55,880
All right.

16
00:00:56,660 --> 00:01:06,800
Now let's go ahead and initialize the first row and first column with the values that we need.

17
00:01:06,800 --> 00:01:12,860
So we have discussed in the previous video that for the first row like let's say there are five columns.

18
00:01:12,860 --> 00:01:18,020
So in that case the values that we need in the first row are 012, three, four.

19
00:01:18,020 --> 00:01:24,290
Similarly, if there are let's say five rows, then the values that we would need in the first column

20
00:01:24,290 --> 00:01:26,150
are zero, one two, three, four okay.

21
00:01:26,150 --> 00:01:27,830
So let's go ahead and implement that.

22
00:01:27,830 --> 00:01:36,140
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.

23
00:01:36,140 --> 00:01:38,300
Because we have n plus one rows.

24
00:01:38,300 --> 00:01:43,160
And then let me say d p at I zero okay is equal to I.

25
00:01:43,190 --> 00:01:45,950
Now over here we are keeping the column value the same.

26
00:01:45,950 --> 00:01:48,260
And we are changing the row values okay.

27
00:01:48,260 --> 00:01:53,210
So this over here helps us initialize the values for the first column.

28
00:01:53,210 --> 00:01:55,640
Now let's do the same thing for the first row.

29
00:01:55,640 --> 00:02:04,580
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

30
00:02:04,580 --> 00:02:04,910
okay.

31
00:02:04,910 --> 00:02:11,210
And we have j plus plus and over here and say depee at zero j is equal to j.

32
00:02:11,480 --> 00:02:11,900
Okay.

33
00:02:11,900 --> 00:02:15,620
So this helps us initialize the values in the first row.

34
00:02:15,620 --> 00:02:21,290
Now that we are done with this, let's go ahead and iterate over the remaining cells in the DP table.

35
00:02:21,290 --> 00:02:23,720
And for that we will use a nested for loop.

36
00:02:23,720 --> 00:02:30,020
So I'll say for let I is equal to one I less than or equal to n I plus plus.

37
00:02:30,020 --> 00:02:37,520
And then we can say for let j is equal to one j less than or equal to m j plus plus.

38
00:02:38,480 --> 00:02:39,050
Okay.

39
00:02:39,050 --> 00:02:43,880
And again what we are going to do is we're going to check whether the characters that we are comparing

40
00:02:43,880 --> 00:02:46,220
in word one and word two are equal.

41
00:02:46,220 --> 00:02:49,700
And if they are equal then we do not need any operation.

42
00:02:49,700 --> 00:02:55,040
So we can just say dp at I j in that case would be dp at I minus one, j minus one.

43
00:02:55,040 --> 00:02:55,370
Okay.

44
00:02:55,370 --> 00:02:56,990
So let's first implement that.

45
00:02:56,990 --> 00:03:02,810
And if that is not the case like if the characters are not equal we proceed and calculate replace delete

46
00:03:02,810 --> 00:03:03,650
and insert.

47
00:03:03,650 --> 00:03:07,130
And we assign the minimum among these three to dp at I j.

48
00:03:07,220 --> 00:03:11,690
So I can say if word one dot char.

49
00:03:12,650 --> 00:03:15,590
Hat I minus one okay.

50
00:03:15,590 --> 00:03:22,640
If this is equal to word two dot chart j minus one.

51
00:03:22,640 --> 00:03:32,300
So if these two characters are equal then we can just say dp at I, j is equal to dp at I minus one

52
00:03:32,780 --> 00:03:33,800
j minus one.

53
00:03:33,800 --> 00:03:34,370
All right.

54
00:03:34,370 --> 00:03:38,240
Now again remember over here we have I minus one and j minus one.

55
00:03:38,240 --> 00:03:42,080
Because the words which are given to us they are zero indexed okay.

56
00:03:42,080 --> 00:03:48,740
So to convert the respective value of I and j which we are getting from the DP table in terms of a zero

57
00:03:48,740 --> 00:03:54,020
indexed value, which is the case for word one and word two, we have to subtract one okay.

58
00:03:54,020 --> 00:03:57,410
So that's why we are doing I minus one and J minus one over here.

59
00:03:57,410 --> 00:04:03,200
Now if this is not the case that is if these two characters are not equal then we'll have to go ahead

60
00:04:03,200 --> 00:04:04,760
and find replace.

61
00:04:05,240 --> 00:04:07,610
And we'll also have to find delete.

62
00:04:09,450 --> 00:04:10,170
Okay.

63
00:04:10,350 --> 00:04:13,380
And we will also have to find insert.

64
00:04:14,270 --> 00:04:20,420
And finally we'll just say dp at ij is equal to math dot min.

65
00:04:21,020 --> 00:04:27,020
And then we'll have these three values over here replace delete op and insert.

66
00:04:27,620 --> 00:04:28,190
Okay.

67
00:04:28,190 --> 00:04:31,820
So replace would be one plus.

68
00:04:32,090 --> 00:04:37,100
And again we have one plus in all of these three cases because it's one operation right.

69
00:04:37,100 --> 00:04:38,420
So that's why we have one plus.

70
00:04:38,420 --> 00:04:43,220
And in the case of replace we have seen that we have to move both the indices.

71
00:04:43,220 --> 00:04:47,420
So we would have DP at I minus one J minus one over here.

72
00:04:47,660 --> 00:04:53,390
Now in the case of delete we have seen that we only have to move the first index.

73
00:04:53,390 --> 00:04:57,440
So we will have DP at I minus one and j over here.

74
00:04:57,440 --> 00:05:01,220
And in the case of insert we will have to only move index two.

75
00:05:01,220 --> 00:05:04,910
So this would be DP at I and you have j minus one.

76
00:05:05,600 --> 00:05:06,680
All right that's it.

77
00:05:06,680 --> 00:05:09,080
So this will help us to fill the DP array.

78
00:05:09,080 --> 00:05:18,050
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

79
00:05:18,050 --> 00:05:18,830
the DP array.

80
00:05:18,830 --> 00:05:20,450
So this should take care of it.

81
00:05:20,450 --> 00:05:24,500
Now let's go ahead and run this code and see if it's passing all the test cases.

82
00:05:27,760 --> 00:05:28,120
All right.

83
00:05:28,120 --> 00:05:28,780
So there's an error.

84
00:05:28,780 --> 00:05:31,600
So I have made a typo over here.

85
00:05:31,630 --> 00:05:32,230
Okay.

86
00:05:32,230 --> 00:05:35,380
So let's correct that and let's again run it.

87
00:05:36,520 --> 00:05:38,230
And you can see that it's working.

88
00:05:38,230 --> 00:05:39,820
It's passing all the test cases.

89
00:05:39,820 --> 00:05:44,020
So this is the tabulation approach for solving the edit distance question.