1
00:00:01,160 --> 00:00:07,490
Let's now write the pseudo code for the second tabulation approach for solving palindrome partitioning.

2
00:00:07,520 --> 00:00:07,910
Two.

3
00:00:07,940 --> 00:00:13,700
The first step for this approach would be to build a 2D array called is palindrome.

4
00:00:13,700 --> 00:00:19,370
And we will make use of this to check whether a substring that we are considering is a palindrome or

5
00:00:19,370 --> 00:00:19,730
not.

6
00:00:19,730 --> 00:00:22,820
So again this is something that we have done multiple times previously.

7
00:00:22,820 --> 00:00:25,340
So we are not going to focus on this over here.

8
00:00:25,340 --> 00:00:30,110
So once we have built this 2D array called is palindrome.

9
00:00:30,110 --> 00:00:32,450
We will proceed with this part over here.

10
00:00:32,450 --> 00:00:36,830
So as we have discussed initially we will just consider this string.

11
00:00:36,830 --> 00:00:38,900
Then we will consider this string.

12
00:00:38,900 --> 00:00:42,680
Then we will proceed and consider this string and go on in that manner.

13
00:00:42,680 --> 00:00:47,510
So notice over here in each of these cases the start value is zero.

14
00:00:47,510 --> 00:00:49,910
But the end value is getting moved.

15
00:00:49,910 --> 00:00:55,820
And in that manner we will be considering strings which are bigger and bigger till we reach the original

16
00:00:55,820 --> 00:00:56,330
problem.

17
00:00:56,330 --> 00:01:01,400
So for this we will have a for loop and let's use the variable end.

18
00:01:01,400 --> 00:01:05,630
So the variable end will go from zero up to n minus one.

19
00:01:05,630 --> 00:01:12,470
Now notice that for a string that we are considering, we can find the maximum number of cuts by just

20
00:01:12,470 --> 00:01:15,140
saying that cuts is equal to end.

21
00:01:15,140 --> 00:01:22,490
For example, if you are considering a, b, a, and at this point n would be equal to two and the maximum

22
00:01:22,490 --> 00:01:25,160
cuts that we can do over here is one two.

23
00:01:25,190 --> 00:01:29,180
So the maximum cuts for a substring is equal to end.

24
00:01:29,210 --> 00:01:31,430
Then we would need another variable.

25
00:01:31,430 --> 00:01:32,990
Let's call it start.

26
00:01:32,990 --> 00:01:37,520
And start will take the values from zero up to end again.

27
00:01:37,520 --> 00:01:38,660
Why is this required.

28
00:01:38,660 --> 00:01:42,170
Because remember let's say we are dealing with this substring over here.

29
00:01:42,170 --> 00:01:46,640
Remember we had a start variable that was initially pointing to index zero.

30
00:01:46,640 --> 00:01:50,270
And then we would move it to index one and then to index two.

31
00:01:50,270 --> 00:01:51,680
And then to index three.

32
00:01:51,680 --> 00:01:57,980
And at each of these points we would check whether the substring from start to end is a palindrome or

33
00:01:57,980 --> 00:01:58,280
not.

34
00:01:58,280 --> 00:02:00,980
So we have seen this previously in the dry run.

35
00:02:00,980 --> 00:02:04,220
So for this we have for start from zero to end.

36
00:02:04,220 --> 00:02:09,890
And then for each combination of start and end, we will check whether the substring from start to end

37
00:02:09,920 --> 00:02:15,680
is a palindrome, and if it is a palindrome, we will try to calculate the number of cuts required for

38
00:02:15,680 --> 00:02:20,450
this scenario, which would equal one plus depee at start minus one.

39
00:02:20,450 --> 00:02:21,950
Now this over here.

40
00:02:21,950 --> 00:02:24,650
This one over here is because we are making a cut.

41
00:02:24,650 --> 00:02:32,330
Let's say we are considering a b a a, and when start is equal to two and end is equal to three, we

42
00:02:32,330 --> 00:02:33,770
see that this is a palindrome.

43
00:02:33,770 --> 00:02:36,740
So we see that let's say start to end is a palindrome.

44
00:02:36,740 --> 00:02:39,530
And in this case we would make a cut over here.

45
00:02:39,530 --> 00:02:44,300
And we don't need to do any cuts in this part because this is a palindrome.

46
00:02:44,300 --> 00:02:46,760
And we have to do one cut over here.

47
00:02:46,760 --> 00:02:48,380
That's why we have one over here.

48
00:02:48,380 --> 00:02:54,770
And then we need to know how many cuts would be required for the previous part, which is DP at start

49
00:02:54,770 --> 00:02:55,610
minus one.

50
00:02:55,880 --> 00:03:00,020
That's how we are getting one plus DP at start minus one.

51
00:03:00,020 --> 00:03:02,720
And then we also could do a cut over here.

52
00:03:02,720 --> 00:03:09,140
So that's why cuts is equal to minimum between cuts and one plus DP at start minus one.

53
00:03:09,140 --> 00:03:15,140
Because we are considering all the possible ways in which the string towards the right is a palindrome.

54
00:03:15,140 --> 00:03:22,820
And then once start, has taken all the values from zero to end, whatever value is there in cuts would

55
00:03:22,820 --> 00:03:28,850
be the minimum number of cuts required for a string that goes from zero up to end.

56
00:03:28,880 --> 00:03:35,810
Therefore, over here we can say dp at end is equal to cuts, and in this manner we will be able to

57
00:03:35,810 --> 00:03:37,580
fill the DP table over here.

58
00:03:37,580 --> 00:03:44,120
And finally we would just need to return the last value in the DP table, which would be our answer.

59
00:03:44,120 --> 00:03:47,120
Therefore, we can return dp at n minus one.

60
00:03:47,120 --> 00:03:52,400
So this is the pseudocode for the approach that we have discussed for solving palindrome partitioning

61
00:03:52,430 --> 00:03:54,920
two using a 1D DP table.