1
00:00:00,110 --> 00:00:01,010
Welcome back.

2
00:00:01,010 --> 00:00:07,310
Let's now get into the code for this space optimized tabulation approach for solving the edit distance

3
00:00:07,310 --> 00:00:07,790
question.

4
00:00:07,790 --> 00:00:14,030
So this over here is the code that we had previously written for implementing the tabulation approach

5
00:00:14,030 --> 00:00:19,220
for solving the edit distance question, but for the space optimized approach, as we have discussed

6
00:00:19,220 --> 00:00:26,150
in the previous video, we will not be using a 2D DP array, but rather we will be using two one dimensional

7
00:00:26,150 --> 00:00:26,660
arrays.

8
00:00:26,660 --> 00:00:28,610
Let's call it prev and curr.

9
00:00:28,640 --> 00:00:29,150
Okay.

10
00:00:29,150 --> 00:00:33,500
And both these arrays will have the size m plus one.

11
00:00:33,500 --> 00:00:38,540
And we will just fill the value zero in every cell in both of these arrays.

12
00:00:38,540 --> 00:00:40,400
So let's go ahead and do that.

13
00:00:40,400 --> 00:00:42,980
So we have prev and then we have curr okay.

14
00:00:42,980 --> 00:00:46,430
And both of them are arrays of size m plus one.

15
00:00:46,430 --> 00:00:50,690
And we have filled the value zero in every cell in these two arrays.

16
00:00:50,870 --> 00:00:51,980
Now let's proceed.

17
00:00:51,980 --> 00:00:58,160
Now we would not need this part over here which was earlier used to initialize the first column okay.

18
00:00:58,160 --> 00:00:59,480
So let's remove this.

19
00:00:59,480 --> 00:01:05,690
But we would still need to initialize the first row which in this case is equal to prev okay.

20
00:01:05,690 --> 00:01:06,740
So we have done that.

21
00:01:06,740 --> 00:01:08,750
Now let's proceed with the iteration.

22
00:01:08,750 --> 00:01:11,930
So over here we have this loop for I okay.

23
00:01:11,930 --> 00:01:14,600
So I goes from one up to n.

24
00:01:14,600 --> 00:01:18,830
Now as we keep going from one row to the next row okay.

25
00:01:18,830 --> 00:01:25,070
We would have to implement a line of code over here which takes care of filling curve at zero.

26
00:01:25,070 --> 00:01:31,970
Now earlier that was taken care when we iterated through the cells in the first column and we initialized

27
00:01:31,970 --> 00:01:32,150
it.

28
00:01:32,150 --> 00:01:34,160
But we have removed that part of the code over here.

29
00:01:34,160 --> 00:01:34,430
Right.

30
00:01:34,430 --> 00:01:41,570
So over here we don't need to initialize many cells, but just the first cell of car at every instance

31
00:01:41,570 --> 00:01:43,310
whenever the value of I changes.

32
00:01:43,310 --> 00:01:44,330
So let's do that.

33
00:01:44,330 --> 00:01:48,410
So over here we can say car at zero is equal to I okay.

34
00:01:48,410 --> 00:01:49,760
So that takes care of it.

35
00:01:49,760 --> 00:01:52,220
So for example visualize it in this manner.

36
00:01:52,220 --> 00:01:59,810
Let's say a row was the row with the index two when we implemented the 2D Depee tabulation approach

37
00:01:59,810 --> 00:02:00,170
okay.

38
00:02:00,170 --> 00:02:05,450
In that case the first cell in that particular row would have the value two.

39
00:02:05,450 --> 00:02:07,700
But now we just have car right.

40
00:02:07,700 --> 00:02:10,250
And we still need the value two over there.

41
00:02:10,250 --> 00:02:12,770
And that's what is taken care over here.

42
00:02:12,800 --> 00:02:15,740
Now once that is done we proceed as usual.

43
00:02:15,740 --> 00:02:18,380
We check whether the two characters are the same.

44
00:02:18,380 --> 00:02:24,800
If they are the same, then over here we have DP at I and instead of DP at I, we replace this with

45
00:02:24,800 --> 00:02:25,100
curve.

46
00:02:25,100 --> 00:02:27,080
So that's what we have to do, right?

47
00:02:27,080 --> 00:02:33,440
Wherever we have DP at, I will change it to curve and wherever we have DP at, I minus one will change

48
00:02:33,440 --> 00:02:34,130
it to pref.

49
00:02:34,130 --> 00:02:38,030
So that's how we can implement the space optimized tabulation approach.

50
00:02:38,030 --> 00:02:40,850
And you can see that's the case over here as well.

51
00:02:40,850 --> 00:02:42,530
So we have DP at I minus one.

52
00:02:42,530 --> 00:02:44,420
So let's change this to pref.

53
00:02:44,420 --> 00:02:47,120
And we have DP I minus one over here as well.

54
00:02:47,120 --> 00:02:49,580
So let's change this also to pref.

55
00:02:49,670 --> 00:02:53,510
And we have uh over here DP at I.

56
00:02:53,690 --> 00:02:55,610
So this changes to cur.

57
00:02:55,760 --> 00:02:58,160
And finally we have DP at IJ over here.

58
00:02:58,160 --> 00:02:59,900
And that changes to car at J.

59
00:03:01,060 --> 00:03:07,690
Okay, so wherever we had DP at IE, we changed it to Kur and wherever we had DP at I minus one we changed

60
00:03:07,690 --> 00:03:08,290
it to pref.

61
00:03:08,290 --> 00:03:09,760
So that's what we have done over here.

62
00:03:09,760 --> 00:03:10,750
Now let's proceed.

63
00:03:10,750 --> 00:03:16,510
And one more important thing that we have to do over here is that whenever we are done iterating through

64
00:03:16,510 --> 00:03:23,380
the respective values of j for a particular value of I, we have to make a copy of cur at that particular

65
00:03:23,380 --> 00:03:25,720
instance and assign it to pref.

66
00:03:25,930 --> 00:03:26,200
Okay.

67
00:03:26,200 --> 00:03:27,430
So let's do that over here.

68
00:03:27,430 --> 00:03:31,450
So prev is equal to and we make a copy of cur and assign it to pref.

69
00:03:31,450 --> 00:03:36,610
So in this way we update the previous array to be the current array at this point okay.

70
00:03:36,610 --> 00:03:37,780
And then we proceed.

71
00:03:37,780 --> 00:03:42,340
Now once we are out of this for loop we will just return prev at m.

72
00:03:43,120 --> 00:03:43,930
And that's it.

73
00:03:43,930 --> 00:03:48,370
Now you may think why do we return prev at m and not cur at m.

74
00:03:48,370 --> 00:03:50,440
And for that let me give you an example.

75
00:03:50,440 --> 00:03:56,560
And again before we discuss why that is required, let's also take a look at this scenario over here.

76
00:03:56,560 --> 00:04:00,760
Because we assign we make a copy of Cur and assign it to prev.

77
00:04:00,760 --> 00:04:08,410
Whenever we come out of this for loop, prev will have the values which are equal to the latest value

78
00:04:08,410 --> 00:04:08,950
for cur.

79
00:04:08,950 --> 00:04:13,090
Okay, so that's the general case and therefore private M should work.

80
00:04:13,090 --> 00:04:17,650
But again typically you may want to return cur at m because it was written depee at n m.

81
00:04:17,650 --> 00:04:18,100
Right.

82
00:04:18,100 --> 00:04:23,590
And again the reason why that would not work is because for an edge case it would cause a problem.

83
00:04:23,590 --> 00:04:28,150
Like let's say word one is an empty string and word two has one character.

84
00:04:28,150 --> 00:04:34,540
Okay, now, because of the way that we have initialized prev and cur, initially prev and cur would

85
00:04:34,540 --> 00:04:37,450
have two elements and it would be zero comma zero.

86
00:04:37,450 --> 00:04:40,300
So this is let us say cur and this is let us say prev.

87
00:04:40,600 --> 00:04:45,790
And over here we have this for loop which initializes the values for prev.

88
00:04:45,790 --> 00:04:49,390
So prev changes from zero 0 to 0 one.

89
00:04:49,840 --> 00:04:51,460
For this example okay.

90
00:04:51,460 --> 00:04:59,290
And because the length of word one is equal to zero, in this case we would not execute or enter this

91
00:04:59,290 --> 00:05:02,590
for loop at all and directly we would come over here.

92
00:05:02,590 --> 00:05:06,940
So if we were to return caret m we would be returning zero.

93
00:05:06,940 --> 00:05:11,800
Which is wrong in this case because we do need one operation to make these two equal.

94
00:05:11,800 --> 00:05:12,190
Right.

95
00:05:12,190 --> 00:05:15,070
But if we do return private M it is correct.

96
00:05:15,070 --> 00:05:16,000
We are returning one.

97
00:05:16,000 --> 00:05:20,680
And this is correctly handled because we have initialization for prev over here.

98
00:05:20,680 --> 00:05:25,570
So that's why we have to return private M over here to handle this edge case.

99
00:05:25,570 --> 00:05:30,760
And again we have discussed why logically it is sound for the general case as well because we are making

100
00:05:30,760 --> 00:05:33,790
a copy of Cur and assigning it to prev over here.

101
00:05:34,030 --> 00:05:34,990
Now that's it.

102
00:05:34,990 --> 00:05:40,600
So this is the space optimized tabulation approach for solving the edit distance question.

103
00:05:40,600 --> 00:05:44,890
Now let's go ahead and run this code and see if it's passing all the test cases.

104
00:05:46,240 --> 00:05:47,980
And you can see that it's working.

105
00:05:47,980 --> 00:05:49,720
It's passing all the test cases.