1
00:00:00,080 --> 00:00:04,400
Let's now memorize the recursive solution that we have just now discussed.

2
00:00:04,400 --> 00:00:08,930
So in the recursion tree over here notice that one plus AC.

3
00:00:08,930 --> 00:00:11,690
So this is happening over here as well as over here.

4
00:00:11,690 --> 00:00:18,710
So the sub problem AC is being computed multiple times which is also the case over here.

5
00:00:19,400 --> 00:00:25,700
Now if you had a more complex input you will see this happening even more number of times.

6
00:00:25,700 --> 00:00:28,310
So there are overlapping subproblems.

7
00:00:28,310 --> 00:00:34,550
And that's why by just adding a few lines of code and memorizing the recursive solution that we have

8
00:00:34,550 --> 00:00:40,250
written, we will be able to significantly improve the time complexity of the solution.

9
00:00:40,250 --> 00:00:41,810
So let's get started.

10
00:00:41,870 --> 00:00:50,090
Now in the recursive approach, we had used a function called ispalindrome to check whether every substring

11
00:00:50,090 --> 00:00:51,620
was a palindrome or not.

12
00:00:51,620 --> 00:00:57,710
But over here, before we memoize the recursive part, which is what we have written in the previous

13
00:00:57,710 --> 00:01:03,440
video, let's also change the way that we are going to check whether a substring is a palindrome or

14
00:01:03,440 --> 00:01:08,450
not, and we can do that because we have discussed this approach multiple times previously.

15
00:01:08,450 --> 00:01:12,950
So initially let's build a 2D array called is palindrome.

16
00:01:12,950 --> 00:01:20,690
And we will in this array store values true and false for every possible substring of the given string.

17
00:01:20,690 --> 00:01:24,500
So if a substring is a palindrome we will store true.

18
00:01:24,500 --> 00:01:27,860
Otherwise we will store false in this 2d dp table.

19
00:01:27,860 --> 00:01:32,660
And then we will just use this to check whether a substring is a palindrome or not.

20
00:01:32,660 --> 00:01:37,280
Now once we have done this, let's get started with the memoization approach.

21
00:01:37,280 --> 00:01:41,120
So what we will do is we will have another DP table for this.

22
00:01:41,120 --> 00:01:49,010
And for every substring which starts at a start index and goes up to the end index, let's store the

23
00:01:49,010 --> 00:01:55,010
minimum cuts that would be required for partitioning this substring into sub strings, where each substring

24
00:01:55,010 --> 00:01:56,750
is a palindrome in itself.

25
00:01:56,750 --> 00:01:58,160
So we are going to store it.

26
00:01:58,160 --> 00:02:03,530
So for example, when we compute the number of cuts for a c we are going to store it.

27
00:02:03,530 --> 00:02:09,050
And when we encounter it the next time we will not go down over here and compute it, but rather we

28
00:02:09,050 --> 00:02:14,240
will directly return the value by just reading it from the DP array which we have over here.

29
00:02:14,240 --> 00:02:18,110
So as we've discussed for this again we will need a 2d dp array.

30
00:02:18,200 --> 00:02:20,360
So this is the memoization approach.

31
00:02:20,360 --> 00:02:25,670
And as you can see we will just need to add a few lines of code which is to create this DP array.

32
00:02:25,670 --> 00:02:31,760
And then after checking the base case before we implement the recursive case, we will check whether

33
00:02:31,760 --> 00:02:34,430
the value is already computed and stored over here.

34
00:02:34,430 --> 00:02:38,180
And if that is the case, we will just retrieve it and return the value.

35
00:02:38,180 --> 00:02:44,060
And if that is not the case, we will proceed and calculate the value and store it in the DP table before

36
00:02:44,060 --> 00:02:44,960
returning the value.

37
00:02:44,960 --> 00:02:46,940
So this is the memoization approach.

38
00:02:46,940 --> 00:02:51,260
Now let's also try to think of the space and time complexity of this approach.

39
00:02:51,260 --> 00:02:53,000
So as we have discussed.

40
00:02:53,000 --> 00:02:56,660
So we are initially going to build a 2D array called Ispalindrome.

41
00:02:56,660 --> 00:03:01,070
Now this over here is going to take space of the order of n square.

42
00:03:01,070 --> 00:03:05,750
And the time complexity for this operation is also going to be of the order of N square.

43
00:03:05,750 --> 00:03:11,360
Now we have discussed this multiple times previously, so I'm not going to repeat it over here and over

44
00:03:11,360 --> 00:03:12,350
here for this part.

45
00:03:12,350 --> 00:03:17,420
For this 2D array we will again need space of the order of n square.

46
00:03:17,420 --> 00:03:22,910
And the time complexity for this is also going to be of the order of N square.

47
00:03:22,910 --> 00:03:23,930
Now why is that?

48
00:03:23,930 --> 00:03:31,340
So we know that for a string of length n, there can be n into n plus one by two substrings.

49
00:03:31,340 --> 00:03:34,640
So if you expand this, you will have an n square term.

50
00:03:34,640 --> 00:03:38,960
So we can say that this over here is of the order of n square.

51
00:03:38,960 --> 00:03:46,070
So for a string of length n, the number of substrings that can be formed is of the order of n square.

52
00:03:46,070 --> 00:03:54,140
And because we are storing every subproblem that we compute, we are going to process a substring only

53
00:03:54,140 --> 00:03:54,920
one time.

54
00:03:54,920 --> 00:03:58,820
And therefore, because the number of substrings is of the order of n square.

55
00:03:58,820 --> 00:04:04,910
So that's why the time complexity of this part over here is also going to be of the order of n square.

56
00:04:04,910 --> 00:04:11,510
So the total time complexity is this plus this, which ultimately is of the order of n square.

57
00:04:11,510 --> 00:04:16,850
And the total space complexity is this plus this, which again is of the order of n square.