1
00:00:01,070 --> 00:00:07,940
So previously we have discussed the bottom up or tabulation approach for solving the edit distance question.

2
00:00:07,940 --> 00:00:13,400
And we have seen that the time and space complexity were of the order of N into M.

3
00:00:13,400 --> 00:00:18,950
And this is an iterative approach, whereas the memoization solution was a recursive approach.

4
00:00:18,980 --> 00:00:24,200
Now let's come up with the space optimized tabulation approach for solving this question.

5
00:00:24,860 --> 00:00:26,270
So let's get started.

6
00:00:26,390 --> 00:00:34,370
Now this is the table that we filled for solving the question where word one was table and word two

7
00:00:34,370 --> 00:00:35,300
was bell.

8
00:00:35,360 --> 00:00:45,530
Now notice over here to fill every row we only needed values from the previous row or the current row.

9
00:00:45,530 --> 00:00:52,610
So for example for filling this cell with this value we had to evaluate these three values.

10
00:00:52,610 --> 00:00:53,180
Right.

11
00:00:53,180 --> 00:00:56,690
Because this was insert this was replace and this was delete.

12
00:00:56,690 --> 00:00:59,780
So we only needed these values similarly.

13
00:00:59,780 --> 00:01:07,040
For example for filling this cell we only needed this value over here because these two were equal.

14
00:01:07,040 --> 00:01:15,350
So we can observe that we only need to store the values at a previous row for computing the values at

15
00:01:15,350 --> 00:01:17,330
a current row at any instance.

16
00:01:17,330 --> 00:01:25,490
So finally, when we are computing the values in this row, we only need to store the values in this

17
00:01:25,490 --> 00:01:26,900
row, which is the previous row.

18
00:01:26,900 --> 00:01:31,850
And we would not need to store all these values in this way.

19
00:01:31,850 --> 00:01:40,910
We can just have two 1D arrays of size m, where m is the number of characters in the word that we are

20
00:01:40,910 --> 00:01:43,250
keeping over here for columns.

21
00:01:43,250 --> 00:01:49,730
Now, we could even optimize this in a better manner by checking which among the two words that are

22
00:01:49,730 --> 00:01:56,270
given to us is of lower length, and that could be kept over here to represent columns.

23
00:01:56,270 --> 00:02:04,400
And in this way we could get a space complexity, which is of the order of the minimum between n and

24
00:02:04,400 --> 00:02:09,770
m, where n and m are the lengths of word one and word two, respectively.

25
00:02:09,770 --> 00:02:17,330
So the space optimized bottom up approach has a space complexity of the order of the minimum between

26
00:02:17,330 --> 00:02:25,250
N and M, and the time complexity is still of the order of N into M, because we would still have to

27
00:02:25,250 --> 00:02:30,470
go through each of these cells till we arrive over here, which gives us the answer.

28
00:02:30,470 --> 00:02:34,070
So this is the space optimized bottom up approach.

29
00:02:34,070 --> 00:02:36,980
Now we would need to erase curr and prev.

30
00:02:37,640 --> 00:02:43,310
And we would use the values at prev to find the values in a current array.

31
00:02:43,310 --> 00:02:49,580
And then when we proceed to the next array for example let's say we had this over here, these values

32
00:02:49,580 --> 00:02:52,010
over here at prev in the prev array.

33
00:02:52,010 --> 00:02:57,290
And then we use that to calculate these values which would be the curr array.

34
00:02:57,290 --> 00:03:00,920
Then we would move ahead and try to calculate these values.

35
00:03:00,920 --> 00:03:05,990
And we would change the values in the prev array to the curr array at this point.

36
00:03:05,990 --> 00:03:09,110
So this would become the new prev and this would be curr.

37
00:03:09,110 --> 00:03:13,550
And once we are done computing these values this would be changed to prev.

38
00:03:13,550 --> 00:03:15,200
And this would become curr.

39
00:03:15,800 --> 00:03:17,870
And we would compute these values.

40
00:03:17,870 --> 00:03:20,720
And once we are done this would be changed to prev.

41
00:03:20,720 --> 00:03:22,190
And this would be curr.

42
00:03:22,190 --> 00:03:24,260
And we would compute these values.

43
00:03:24,260 --> 00:03:26,600
And finally this would be changed to prev.

44
00:03:26,600 --> 00:03:28,010
And this would be curr.

45
00:03:28,190 --> 00:03:30,710
And we would compute these values.

46
00:03:30,710 --> 00:03:33,080
And we will get the answer over here.

47
00:03:33,800 --> 00:03:38,360
So we have discussed four approaches for solving the edit distance question.

48
00:03:38,360 --> 00:03:45,320
And we have seen that for the space optimized bottom up approach, we had a time complexity of the order

49
00:03:45,320 --> 00:03:53,120
of N into M, and the space complexity was of the order of the minimum between M and N, which is even

50
00:03:53,120 --> 00:03:57,740
better than the simple recursive approach for solving the edit distance question.