1
00:00:00,080 --> 00:00:06,110
Let's now implement the memoization approach that we have discussed in the previous video for the palindrome

2
00:00:06,110 --> 00:00:07,430
partitioning two question.

3
00:00:07,430 --> 00:00:10,010
And let's also make a change over here.

4
00:00:10,010 --> 00:00:14,750
Earlier when we implemented the recursive solution, we had this function over here to check whether

5
00:00:14,750 --> 00:00:17,270
a particular substring is a palindrome or not.

6
00:00:17,270 --> 00:00:18,710
So let's replace this.

7
00:00:18,710 --> 00:00:23,960
And instead of that, let's implement the tabulation approach where we are going to check only once

8
00:00:23,960 --> 00:00:26,810
whether a particular substring is a palindrome or not.

9
00:00:26,810 --> 00:00:27,140
Okay.

10
00:00:27,140 --> 00:00:32,660
So for this let's have a 2D depee table and let me just call it is palindrome.

11
00:00:33,350 --> 00:00:37,640
And again before that, let me say that the length of the given string is equal to n.

12
00:00:37,640 --> 00:00:41,030
So let n is equal to s dot length okay.

13
00:00:41,030 --> 00:00:42,680
And this dp table.

14
00:00:42,680 --> 00:00:46,220
This 2d dp table will be of size n into n.

15
00:00:46,220 --> 00:00:50,870
So I can say array dot from array n okay.

16
00:00:51,650 --> 00:00:54,080
And we also need n columns.

17
00:00:55,040 --> 00:01:02,000
Now let's go ahead and fill every cell in this particular DP table with the value false.

18
00:01:02,810 --> 00:01:03,350
All right.

19
00:01:03,380 --> 00:01:09,530
Now what we're going to do is we're going to iterate through the cells in this S palindrome DP table

20
00:01:09,530 --> 00:01:10,550
lengthwise.

21
00:01:10,550 --> 00:01:16,220
And wherever we encounter a substring that is a palindrome will fill the value true over there.

22
00:01:16,220 --> 00:01:18,290
And this is something that you have done many times.

23
00:01:18,290 --> 00:01:20,810
So you should be pretty familiar with this by now.

24
00:01:20,810 --> 00:01:28,190
So we can say for let L is equal to one l less than or equal to n l plus plus okay.

25
00:01:28,190 --> 00:01:36,260
Because length takes the values from one up to n and then we have for let I is equal to zero I less

26
00:01:36,260 --> 00:01:41,000
than or equal to n minus l I plus plus okay.

27
00:01:41,000 --> 00:01:45,830
And j is going to equal I plus l minus one.

28
00:01:45,830 --> 00:01:51,620
Now for every combination of I and j we have to evaluate whether we are dealing with the palindrome

29
00:01:51,620 --> 00:01:52,160
or not.

30
00:01:52,160 --> 00:01:59,150
So first we will check if I is equal to j then we can just say is palindrome at I.

31
00:01:59,150 --> 00:02:04,730
J is true because we are just dealing with a string which has one character, okay.

32
00:02:04,730 --> 00:02:05,960
And that is a palindrome.

33
00:02:05,960 --> 00:02:12,980
And if that is not the case, we have to check whether s at I is equal to s at j.

34
00:02:12,980 --> 00:02:20,570
And if these are equal, then either we should be dealing with a string which just has two characters.

35
00:02:20,570 --> 00:02:23,480
And for that we can check whether j is equal to I plus one.

36
00:02:23,480 --> 00:02:30,830
Or we will have to check whether the substring that we get after removing the ith and jth character,

37
00:02:30,830 --> 00:02:35,510
or the substring in between the ith and jth character is a palindrome or not.

38
00:02:35,510 --> 00:02:40,490
And because we are doing this iteration lengthwise, we would have already calculated it previously

39
00:02:40,490 --> 00:02:44,540
and we can just check is palindrome I plus one j minus one.

40
00:02:44,540 --> 00:02:44,840
Okay.

41
00:02:44,840 --> 00:02:49,520
So if this is true it would mean that the substring that you get when you remove the ith and jth character

42
00:02:49,520 --> 00:02:50,840
is also a palindrome.

43
00:02:50,870 --> 00:02:56,780
Now if this is the case, that is, if this is true and if either of these conditions is true, then

44
00:02:56,780 --> 00:03:00,020
this particular substring is a palindrome.

45
00:03:00,020 --> 00:03:04,190
And we can say is palindrome I j is equal to true.

46
00:03:04,670 --> 00:03:05,150
All right.

47
00:03:05,180 --> 00:03:10,460
Now if this is not the case then this particular substring is not a palindrome.

48
00:03:10,910 --> 00:03:11,540
That's it.

49
00:03:11,540 --> 00:03:15,470
Now you can either say is palindrome I j is equal to false.

50
00:03:15,470 --> 00:03:20,270
Or you can just leave it as well because initially we have initialized every cell with the value false.

51
00:03:20,270 --> 00:03:22,760
But I'm just writing it over here for clarity's sake.

52
00:03:22,760 --> 00:03:28,610
So as of now we have iterated lengthwise through the is palindrome table DP table that we have created

53
00:03:28,610 --> 00:03:29,120
over here.

54
00:03:29,120 --> 00:03:34,970
And for every cell that represents a substring that is a palindrome, we have filled the value true

55
00:03:34,970 --> 00:03:35,540
over there.

56
00:03:35,540 --> 00:03:38,360
Now we would need one more DP table.

57
00:03:38,360 --> 00:03:40,550
Let's just call it min cuts okay.

58
00:03:40,820 --> 00:03:42,410
So let's call it min cuts.

59
00:03:42,410 --> 00:03:49,700
And in this table we will store the minimum cuts required for every substring to ensure that it's partitioned

60
00:03:49,700 --> 00:03:51,950
in a way that every partition is a palindrome.

61
00:03:51,980 --> 00:03:58,160
Now this DP table over here, which is min cuts, is also going to have n rows and n columns.

62
00:03:58,160 --> 00:04:02,690
So I can say array dot from array n okay.

63
00:04:03,110 --> 00:04:05,720
And it also needs n columns.

64
00:04:07,220 --> 00:04:13,520
And we will fill every cell in this DP table over here with null okay.

65
00:04:13,520 --> 00:04:15,890
Now let's go ahead and write the main function.

66
00:04:15,890 --> 00:04:20,180
So we have this partitions function over here which we had previously written.

67
00:04:20,180 --> 00:04:25,250
Now we're going to slightly modify this to ensure that this solution is the memoization solution.

68
00:04:25,250 --> 00:04:28,400
So first we have the base case over here where the start is equal to end.

69
00:04:28,400 --> 00:04:32,510
And whether the substring which is given to us is a palindrome or not.

70
00:04:32,510 --> 00:04:34,310
And in which case we return zero.

71
00:04:34,310 --> 00:04:37,040
So there is no change logically in the base case.

72
00:04:37,040 --> 00:04:41,690
But because we have changed the way that we check whether a substring is a palindrome or not.

73
00:04:41,690 --> 00:04:44,630
So we would have to change that, because initially we had a function.

74
00:04:44,630 --> 00:04:48,470
But now we are going to use this particular DP table over here okay.

75
00:04:48,470 --> 00:04:54,770
So I'll say is palindrome at start and end okay.

76
00:04:55,400 --> 00:05:00,950
Now if this is true it would mean that yes, this particular string which is given to us is a palindrome.

77
00:05:00,950 --> 00:05:02,450
So this is the base case.

78
00:05:02,450 --> 00:05:05,210
Now we just had a slight tweak over here.

79
00:05:05,210 --> 00:05:11,240
Now after the base case before we go ahead over here and do these computations, we will first check

80
00:05:11,240 --> 00:05:16,370
whether we had already computed and stored the number of cuts required for this particular substring

81
00:05:16,370 --> 00:05:16,940
at hand.

82
00:05:16,940 --> 00:05:25,280
And for that we will just make use of this dp table min cuts, and we will see whether if min cuts at

83
00:05:25,280 --> 00:05:32,540
start end is not equal to null okay.

84
00:05:32,540 --> 00:05:32,660
We.

85
00:05:32,770 --> 00:05:38,410
Because over here, notice we had filled every cell in this deep table with the value null.

86
00:05:38,410 --> 00:05:42,850
But if we see over here that min cuts at start end is not equal to null.

87
00:05:42,880 --> 00:05:48,820
The reason for this would be that we already previously computed this and we stored it in this particular

88
00:05:48,820 --> 00:05:49,210
table.

89
00:05:49,210 --> 00:05:49,600
Okay.

90
00:05:49,600 --> 00:05:55,900
Now if that is the case then we don't need to recompute it, but rather we will just return min cuts

91
00:05:55,900 --> 00:05:57,220
at start end.

92
00:05:58,840 --> 00:05:59,500
Okay.

93
00:05:59,500 --> 00:06:01,840
Now, if this is not the case, then we proceed.

94
00:06:01,840 --> 00:06:05,770
We have the maximum value assigned to minimum cuts over here.

95
00:06:05,770 --> 00:06:07,540
And then we have this for loop.

96
00:06:07,540 --> 00:06:11,260
We calculate the minimum cuts over here and over here.

97
00:06:11,260 --> 00:06:13,750
Before we return it we are going to store it.

98
00:06:13,750 --> 00:06:24,490
So we can say min cuts at start end is equal to whatever we get over here which is minimum cuts okay.

99
00:06:24,490 --> 00:06:26,740
And then we will just return this.

100
00:06:29,140 --> 00:06:29,470
All right.

101
00:06:29,470 --> 00:06:30,100
So that's it.

102
00:06:30,100 --> 00:06:36,880
So with just a few tweaks we were able to convert the recursive solution to the memoization solution.

103
00:06:36,880 --> 00:06:42,790
And we have also implemented a tabulation approach over here to calculate whether a substring is a palindrome

104
00:06:42,790 --> 00:06:43,390
or not.

105
00:06:43,390 --> 00:06:49,360
And that helps us to improve the time complexity because we are checking whether a particular substring

106
00:06:49,360 --> 00:06:51,430
is a palindrome or not only one type.

107
00:06:51,430 --> 00:06:55,270
Now let's go ahead and run this code and see if it's passing all the test cases.

108
00:06:56,230 --> 00:06:56,590
All right.

109
00:06:56,590 --> 00:06:57,520
So there's an error.

110
00:06:57,550 --> 00:07:01,150
Now again the error is because over here is palindrome.

111
00:07:01,150 --> 00:07:03,610
In the previous implementation it was a function right.

112
00:07:03,610 --> 00:07:05,920
But over here we have changed it to a table.

113
00:07:05,920 --> 00:07:07,270
And I forgot to change this.

114
00:07:07,270 --> 00:07:08,500
So let's change this.

115
00:07:08,500 --> 00:07:12,700
So this should be is palindrome at start and end index.

116
00:07:14,670 --> 00:07:15,120
Okay.

117
00:07:15,120 --> 00:07:16,440
So this should solve it.

118
00:07:16,440 --> 00:07:20,220
Now let's go ahead and again run this and see if it's passing all the test cases.

119
00:07:20,940 --> 00:07:22,560
And you can see that it's working.

120
00:07:22,560 --> 00:07:24,270
It's passing all the test cases.

121
00:07:24,780 --> 00:07:29,190
So this is the memoization approach for solving palindrome partitioning two.