1 00:00:00,260 --> 00:00:07,160 In the previous videos, we have discussed the recursive approach for solving the LCS question, and 2 00:00:07,160 --> 00:00:12,980 we have discussed that the time complexity of this approach is of the order of two to the power n plus 3 00:00:12,980 --> 00:00:17,780 m, and the space complexity is of the order of N plus m. 4 00:00:17,810 --> 00:00:24,860 Let's now discuss the memoization or top down approach for solving the LCS question, and we'll see 5 00:00:24,860 --> 00:00:28,910 that we'll just have to add a few lines of code to achieve this. 6 00:00:28,910 --> 00:00:33,530 So let's get started now for discussing the memoization approach. 7 00:00:33,530 --> 00:00:35,030 Let's take an example. 8 00:00:35,030 --> 00:00:42,440 So let's take the two strings which are given to us as a, b, c, d, e, f and a c, f. 9 00:00:42,440 --> 00:00:50,450 Now we will need a 2D array to store things that we compute so that we don't compute it again and again. 10 00:00:50,450 --> 00:00:53,210 So over here I have a 2D array. 11 00:00:53,210 --> 00:00:57,890 Notice that I have a c f over here in the columns. 12 00:00:57,890 --> 00:01:01,010 And I have a, b, c, d e f in the rows. 13 00:01:01,010 --> 00:01:04,160 So this is one string and this is the other string. 14 00:01:04,160 --> 00:01:11,570 Now you could change the position of the two strings and have ACF as rows and a, b, C, D, f as columns. 15 00:01:11,570 --> 00:01:12,740 That does not matter. 16 00:01:12,740 --> 00:01:14,900 Now let's write the indices over here. 17 00:01:14,900 --> 00:01:17,120 So that's zero one and two. 18 00:01:17,120 --> 00:01:22,370 And the indices over here are zero, one, two three, four and five. 19 00:01:22,370 --> 00:01:26,810 Now in this table what does each cell represent. 20 00:01:26,810 --> 00:01:30,200 For example what does this cell represent. 21 00:01:30,200 --> 00:01:40,730 This cell represents the subproblem where we have a b, c as one string and a c as the other string. 22 00:01:40,730 --> 00:01:42,770 So that's this subproblem over here. 23 00:01:42,770 --> 00:01:44,780 Now what would be another subproblem. 24 00:01:44,780 --> 00:01:46,340 Let's take this one for example. 25 00:01:46,340 --> 00:01:54,410 So this would be the subproblem where we have a b c d e f as one string and we have a c as the other 26 00:01:54,410 --> 00:01:54,890 string. 27 00:01:54,890 --> 00:01:57,320 Or what would be this subproblem? 28 00:01:57,320 --> 00:02:05,120 This subproblem has only a b as one string and a c f as the other string. 29 00:02:05,120 --> 00:02:09,350 So that's what each cell in this 2D table represents. 30 00:02:09,380 --> 00:02:14,210 Now let's go ahead and see how we can implement the memoization approach. 31 00:02:14,840 --> 00:02:21,530 So the idea of the memoization approach is that it's still recursive in nature. 32 00:02:21,530 --> 00:02:27,680 But whenever we are asked to find the answer to a subproblem, we will check whether we have already 33 00:02:27,680 --> 00:02:30,110 computed it and stored it in this table. 34 00:02:30,110 --> 00:02:36,440 If it's there, which can be found out by checking whether the value at that particular place in the 35 00:02:36,440 --> 00:02:38,630 table is not minus one. 36 00:02:38,630 --> 00:02:43,520 So if it's not minus one, we will just take that value and return it. 37 00:02:43,520 --> 00:02:45,830 And that's just a constant time operation. 38 00:02:45,830 --> 00:02:52,790 But if it's not there, we go ahead and compute the value and we store it and then return the value. 39 00:02:52,790 --> 00:02:56,780 So we will compute every subproblem only one time. 40 00:02:56,780 --> 00:02:59,780 So that's the core idea to memoize this. 41 00:02:59,780 --> 00:03:07,010 So when we write the code for this, after checking the base case, before we go ahead and do the computation, 42 00:03:07,010 --> 00:03:12,350 which is the recursive case, we would check whether the value at that particular position in the 2D 43 00:03:12,350 --> 00:03:14,540 table is not minus one. 44 00:03:14,540 --> 00:03:17,540 If it's not minus one, we just return the value. 45 00:03:17,540 --> 00:03:19,250 So that's the memoization approach. 46 00:03:19,250 --> 00:03:23,600 And again there's just a few tweaks to the recursive approach that we have just now discussed. 47 00:03:23,600 --> 00:03:27,380 And we will again discuss this when we implement the code of this. 48 00:03:27,380 --> 00:03:31,220 Now what would be the space and time complexity of this approach. 49 00:03:31,220 --> 00:03:36,080 Now notice that the memoization approach is still recursive in nature. 50 00:03:36,080 --> 00:03:39,920 So we will take up space on the recursive call stack. 51 00:03:39,920 --> 00:03:43,130 And we also need space for this 2D array. 52 00:03:43,190 --> 00:03:50,990 So that's why the space complexity is of the order of n into m plus the order of n plus m. 53 00:03:50,990 --> 00:03:53,060 So this is for the table over here. 54 00:03:53,790 --> 00:03:58,830 And this over here is for the space used on the recursive call stack. 55 00:03:58,860 --> 00:04:05,970 Now, we have already discussed why this is of the order of n plus m when we discuss this for the recursive 56 00:04:05,970 --> 00:04:06,570 approach. 57 00:04:06,570 --> 00:04:14,640 So again, because n into m is greater than n plus m, we can say that the space complexity is of the 58 00:04:14,640 --> 00:04:16,440 order of n into m. 59 00:04:16,650 --> 00:04:18,780 Now what about the time complexity? 60 00:04:18,780 --> 00:04:26,370 The time complexity will be of the order of n into M, because that's the upper bound, or the maximum 61 00:04:26,370 --> 00:04:29,400 number of subproblems that we would want to compute. 62 00:04:29,400 --> 00:04:31,440 And that's each of these cells over here. 63 00:04:31,440 --> 00:04:34,350 Now typically we would not need all the subproblems. 64 00:04:34,350 --> 00:04:37,170 But again we're just trying to find the upper bound. 65 00:04:37,170 --> 00:04:42,900 And that's why the time complexity of this solution is of the order of n into m.