1
00:00:00,490 --> 00:00:01,600
Welcome back.

2
00:00:01,600 --> 00:00:07,540
We have discussed the recursive approach for solving the edit distance question, and we have seen that

3
00:00:07,540 --> 00:00:15,310
the space complexity for that solution was of the order of n plus M, and the time complexity was of

4
00:00:15,310 --> 00:00:17,800
the order of three to the power n plus m.

5
00:00:17,800 --> 00:00:21,130
Now, this definitely is not a great time complexity.

6
00:00:21,130 --> 00:00:23,050
And let's see if we can do better.

7
00:00:23,050 --> 00:00:26,650
So let's proceed with the memoization approach.

8
00:00:26,650 --> 00:00:30,310
Remember memoization is just recursion plus storage.

9
00:00:30,310 --> 00:00:32,020
So let's take a look at how.

10
00:00:32,020 --> 00:00:39,250
By just adding a few lines of code, we will be able to memorize the recursive solution and arrive at

11
00:00:39,250 --> 00:00:41,380
a much better time complexity.

12
00:00:41,380 --> 00:00:46,150
For discussing the memoization approach, let's take an example.

13
00:00:46,150 --> 00:00:48,730
Let's say we want to convert table to bell.

14
00:00:48,730 --> 00:00:51,640
So we would need a 2d dp array.

15
00:00:51,640 --> 00:00:56,050
And we have rows for every character in word one.

16
00:00:56,050 --> 00:00:59,380
And we have columns for every character in word two.

17
00:00:59,380 --> 00:01:05,170
Now of course you could reverse the position of table and bell, but again either way works.

18
00:01:05,170 --> 00:01:07,420
Now let's write the indices over here.

19
00:01:07,420 --> 00:01:09,550
So we have 012.

20
00:01:09,550 --> 00:01:11,950
And over here we have 01234.

21
00:01:11,950 --> 00:01:18,370
Now before we go ahead and discuss this approach, let's quickly discuss what each cell represents.

22
00:01:18,370 --> 00:01:25,840
For example, what does this cell over here represent or what subproblem does this cell represent.

23
00:01:25,840 --> 00:01:33,370
So this cell over here represents this subproblem where we have t e, b, l and b.

24
00:01:33,400 --> 00:01:35,950
So that is what this subproblem represents.

25
00:01:35,950 --> 00:01:37,150
In a similar manner.

26
00:01:37,150 --> 00:01:46,390
This cell over here would represent t e and B or this cell over here would represent t e and b e l.

27
00:01:46,390 --> 00:01:53,080
And again the approach in memoization is that we will compute a subproblem only one time.

28
00:01:53,080 --> 00:02:00,610
And then we would store it so that if we encounter it at a future time, we would just return the value

29
00:02:00,610 --> 00:02:04,480
in constant time and we would not have the need to compute it.

30
00:02:04,480 --> 00:02:09,880
So again, the way that we will approach this is it's just going to be the same recursive approach.

31
00:02:09,880 --> 00:02:13,780
But then initially we have every cell filled with minus one.

32
00:02:13,780 --> 00:02:18,670
And whenever we compute the answer to a subproblem we will store it.

33
00:02:18,670 --> 00:02:26,470
So whenever we have a call first we would check whether the value of that subproblem in the DP table

34
00:02:26,470 --> 00:02:28,630
is equal to minus one or not.

35
00:02:28,630 --> 00:02:34,660
And if we see that it's not equal to minus one, we will just take that value and return it.

36
00:02:34,660 --> 00:02:41,050
And if it is minus one, we will go ahead and we will have recursive calls to compute that value.

37
00:02:41,050 --> 00:02:45,820
But before we return the value we will go ahead and store it in the DP table.

38
00:02:45,820 --> 00:02:51,250
So this is how we can memorize the recursive approach by just adding a few lines of code.

39
00:02:51,250 --> 00:02:56,950
Now let's quickly take a look at the space and time complexity of the memoization approach.

40
00:02:56,950 --> 00:03:03,730
So notice that the upper bound of the maximum number of computations that we would have to do is of

41
00:03:03,730 --> 00:03:09,850
the order of n into n, where n and m are the lengths of the two words that are given to us.

42
00:03:09,850 --> 00:03:16,810
Now, this is the case because at max we would have to do n into m computations, because that's the

43
00:03:16,810 --> 00:03:19,360
number of cells that are there in this DP table.

44
00:03:19,360 --> 00:03:26,410
And if we need a value that we had previously computed, we will not compute it again, but rather we

45
00:03:26,410 --> 00:03:29,620
would just retrieve it from the DP table and return it.

46
00:03:29,620 --> 00:03:34,930
So that's why the time complexity over here is going to be of the order of n into m.

47
00:03:35,110 --> 00:03:42,280
Now, when it comes to the space complexity, it's going to be of the order of n into m plus n plus

48
00:03:42,280 --> 00:03:42,670
m.

49
00:03:42,670 --> 00:03:48,100
Now, we will use this much space over here on the recursive call stack.

50
00:03:48,100 --> 00:03:53,710
And again we have discussed this when we discussed the recursive approach because this is the maximum

51
00:03:53,710 --> 00:03:55,660
depth of the recursion tree.

52
00:03:55,660 --> 00:04:00,520
But then between n m and n plus m n m dominates.

53
00:04:00,520 --> 00:04:07,150
And that's why we can say that the space complexity of this solution is also of the order of n into

54
00:04:07,150 --> 00:04:07,450
m.

55
00:04:07,450 --> 00:04:11,530
And again, this space over here is used for the DP table.