1
00:00:00,080 --> 00:00:00,980
Welcome back.

2
00:00:00,980 --> 00:00:06,980
So this is the recursive solution that we have previously written for solving the edit distance equation.

3
00:00:07,130 --> 00:00:09,560
Now let's go ahead and memorize this.

4
00:00:09,560 --> 00:00:15,110
And you will see that for achieving this we will just have to add a few lines of code.

5
00:00:15,110 --> 00:00:15,590
All right.

6
00:00:15,590 --> 00:00:16,670
So let's get started.

7
00:00:16,670 --> 00:00:19,850
To start with let's create a 2D DP array.

8
00:00:19,850 --> 00:00:22,220
And let me just call it memo okay.

9
00:00:22,220 --> 00:00:27,140
So this is going to be a 2D dp array of size n into m.

10
00:00:27,140 --> 00:00:30,620
So I can say this is equal to array dot from.

11
00:00:31,350 --> 00:00:36,360
And over here I have linked N because we want n rows over here okay.

12
00:00:36,360 --> 00:00:39,090
And we want m columns okay.

13
00:00:39,090 --> 00:00:42,630
So over here we'll have array and the size is m.

14
00:00:42,630 --> 00:00:48,120
And we will fill every cell in this 2D dp array with the value minus one.

15
00:00:48,480 --> 00:00:52,980
And this is something that we typically always do in memoization solutions.

16
00:00:53,220 --> 00:00:53,730
All right.

17
00:00:53,730 --> 00:00:56,190
So we have created our 2D array.

18
00:00:56,190 --> 00:01:01,950
Now let's slightly modify the helper function which is the number of operations function over here.

19
00:01:01,950 --> 00:01:07,080
So after the base case before we proceed over here which is the recursive case.

20
00:01:07,080 --> 00:01:13,830
And before we do these computations we will go ahead and check whether we had already previously computed

21
00:01:13,830 --> 00:01:20,160
this particular subproblem, which is the case where we have the particular values for index one and

22
00:01:20,160 --> 00:01:20,880
index two.

23
00:01:20,880 --> 00:01:26,580
So what we will do is we will check over here if memo at index one.

24
00:01:27,390 --> 00:01:32,400
Index two is not equal to minus one okay.

25
00:01:32,400 --> 00:01:39,420
So if it's not equal to minus one it is not minus one because we computed and stored it because over

26
00:01:39,420 --> 00:01:45,060
here notice we had initially filled every cell in this 2D array with the value minus one.

27
00:01:45,060 --> 00:01:49,710
So if it is not minus one we don't need to go ahead over here and compute it.

28
00:01:49,710 --> 00:01:54,810
But rather we will just return memo at index one.

29
00:01:54,810 --> 00:01:57,090
Index two okay.

30
00:01:57,090 --> 00:01:57,900
And that's it.

31
00:01:57,930 --> 00:02:00,750
Now let's go ahead and take a look at this part over here.

32
00:02:00,870 --> 00:02:07,560
So if this is not the case that is if we had not computed it earlier we come over here and we check

33
00:02:07,560 --> 00:02:09,720
whether these two characters are equal.

34
00:02:09,720 --> 00:02:14,370
And if they are equal we do whatever we have written over here.

35
00:02:14,370 --> 00:02:14,670
Okay.

36
00:02:14,670 --> 00:02:16,440
So that's still the same.

37
00:02:16,440 --> 00:02:19,590
But instead of returning it we are going to first store it.

38
00:02:19,590 --> 00:02:23,070
So over here and say memo at index one.

39
00:02:23,760 --> 00:02:29,010
Index two is equal to whatever we get over here okay.

40
00:02:29,010 --> 00:02:33,540
And if this is not the case we compute insert delete and replace.

41
00:02:33,540 --> 00:02:35,520
And we find the minimum between them.

42
00:02:35,520 --> 00:02:38,250
And we store it in memo at index one.

43
00:02:38,250 --> 00:02:39,180
Index two.

44
00:02:41,900 --> 00:02:42,500
All right.

45
00:02:42,500 --> 00:02:44,630
And then we'll just have to return it.

46
00:02:44,630 --> 00:02:46,070
So let's go ahead and return it.

47
00:02:46,070 --> 00:02:49,160
And again over here notice this is happening.

48
00:02:49,160 --> 00:02:50,960
If these two characters are equal.

49
00:02:50,960 --> 00:02:55,670
And because we don't have a return statement over here, we would need an else statement because we

50
00:02:55,670 --> 00:03:02,390
don't want to calculate, insert, delete and replace in case the two characters that we are comparing

51
00:03:02,390 --> 00:03:03,140
are equal.

52
00:03:03,140 --> 00:03:05,930
So let's copy this and let's put it over here.

53
00:03:07,370 --> 00:03:08,090
All right.

54
00:03:08,870 --> 00:03:14,480
And then finally we would have to return memo at index one.

55
00:03:14,690 --> 00:03:15,560
Index two.

56
00:03:15,920 --> 00:03:16,640
And that's it.

57
00:03:16,640 --> 00:03:21,770
And we have successfully memoized the recursive approach that we had previously implemented.

58
00:03:21,770 --> 00:03:26,150
Now let's go ahead and run this code and see if it's passing all the test cases.

59
00:03:26,690 --> 00:03:28,700
And you can see that it's working.

60
00:03:28,700 --> 00:03:30,380
It's passing all the test cases.

61
00:03:30,380 --> 00:03:34,790
So this is the memoization approach for solving the edit distance question.