1
00:00:00,830 --> 00:00:01,820
Welcome back.

2
00:00:01,850 --> 00:00:07,940
Let's now write the pseudo code for the tabulation approach that we have just now discussed for solving

3
00:00:07,940 --> 00:00:09,500
palindrome partitioning two.

4
00:00:09,530 --> 00:00:12,320
So we have this DP table over here.

5
00:00:12,320 --> 00:00:15,980
And we know that we have to fill it lengthwise.

6
00:00:15,980 --> 00:00:17,960
And we have done this multiple times.

7
00:00:17,960 --> 00:00:26,930
So we can say for length going from one to n and for I from zero to n minus l and j is equal to I plus

8
00:00:26,930 --> 00:00:27,860
l minus one.

9
00:00:27,860 --> 00:00:30,410
So this is something that you have seen multiple times.

10
00:00:30,410 --> 00:00:34,100
And this nested for loop will help us go lengthwise.

11
00:00:34,130 --> 00:00:39,740
Now initially we will check whether I is equal to J which represents these cells.

12
00:00:39,740 --> 00:00:43,940
And if I is equal to j we are dealing with a substring of length one.

13
00:00:43,940 --> 00:00:47,300
And we know that a substring of length one is a palindrome.

14
00:00:47,300 --> 00:00:49,790
So we can just fill zero over here.

15
00:00:49,820 --> 00:00:51,500
Now we proceed.

16
00:00:51,500 --> 00:00:57,800
And if this is not the case we are going to check whether the character at index I is equal to the character

17
00:00:57,800 --> 00:00:58,880
at index j.

18
00:00:58,880 --> 00:01:05,930
And if these are equal, we are going to check whether dp at I plus one and j minus one is equal to

19
00:01:05,930 --> 00:01:06,380
zero.

20
00:01:06,380 --> 00:01:12,560
This means that after we remove these two characters from the string that we are considering, is the

21
00:01:12,560 --> 00:01:14,630
remaining part a palindrome or not?

22
00:01:14,630 --> 00:01:18,260
Or do we just need zero cuts for the remaining part?

23
00:01:18,260 --> 00:01:23,360
So if this is equal to zero, it would indicate that the remaining part is a palindrome, which would

24
00:01:23,360 --> 00:01:26,810
mean that the total substring that we are considering is a palindrome.

25
00:01:26,810 --> 00:01:31,670
And therefore we can say dp at I, j in that case is equal to zero.

26
00:01:31,670 --> 00:01:38,600
Now we proceed, and if this is not the case, then we are going to say dp at I, j is equal to j minus

27
00:01:38,600 --> 00:01:44,840
one, which would indicate the scenario where we would need to do a cut at every possible place.

28
00:01:44,840 --> 00:01:48,710
So this is the maximum value that dp at I, j can take.

29
00:01:48,710 --> 00:01:54,440
And then we are going to take a variable k which goes from I up to j minus one.

30
00:01:54,440 --> 00:02:04,280
And then for each value of k we are going to compute dp at I k plus one plus dp at k plus one j and

31
00:02:04,280 --> 00:02:05,270
dp at I.

32
00:02:05,270 --> 00:02:10,310
J is going to take the minimum value among dp at ij and this value over here.

33
00:02:10,310 --> 00:02:13,490
So initially dp at I, j took the maximum value.

34
00:02:13,490 --> 00:02:17,300
And then when k is equal to I, we will get a value for this.

35
00:02:17,300 --> 00:02:22,400
And between the initial value and this value dp at I, j will take the minimum value.

36
00:02:22,400 --> 00:02:26,780
Then k will take the next possible value among these possible values.

37
00:02:26,780 --> 00:02:29,210
And we are again going to compute this value.

38
00:02:29,210 --> 00:02:33,290
And in this manner we are going to evaluate all these possible values.

39
00:02:33,290 --> 00:02:38,090
And finally dp at I j will take the minimum possible value.

40
00:02:38,090 --> 00:02:45,170
Or we will make the cut at the place where this over here is going to take the minimum possible value.

41
00:02:45,170 --> 00:02:52,100
In this way we will fill dp at ij and then proceeding from cell to cell, we will fill the DP table

42
00:02:52,100 --> 00:02:52,670
over here.

43
00:02:52,670 --> 00:02:56,180
Finally we will have the answer in this cell.

44
00:02:56,180 --> 00:03:00,590
Therefore we will just return dp at zero n minus one.

45
00:03:00,590 --> 00:03:06,440
So this is the pseudocode for the approach that we have discussed which can be used for solving palindrome

46
00:03:06,440 --> 00:03:07,460
partitioning two.