1
00:00:00,140 --> 00:00:01,010
Welcome back.

2
00:00:01,010 --> 00:00:05,960
Let's now implement the tabulation approach for solving palindrome partitioning two.

3
00:00:05,960 --> 00:00:10,100
And over here we will be implementing the approach using a 2D array.

4
00:00:10,100 --> 00:00:14,630
And later we will take a look at the approach which can be taken just using a 1D array.

5
00:00:14,630 --> 00:00:15,200
All right.

6
00:00:15,200 --> 00:00:22,070
So to start with let's say n is the length of the string which is given to us okay.

7
00:00:22,070 --> 00:00:28,790
And we are going to create a DP array which is going to be a 2D array which will have n rows and n columns.

8
00:00:28,790 --> 00:00:37,010
So let's say let dp is equal to array dot from and then you have array n over here.

9
00:00:39,050 --> 00:00:41,450
And we need array and over here as well okay.

10
00:00:41,450 --> 00:00:45,800
So we have created a 2D dp array which has n rows and n columns.

11
00:00:45,800 --> 00:00:51,650
And what we are going to do over here is that we will fill every cell with the value zero okay.

12
00:00:51,650 --> 00:00:53,510
So this is our 2D array.

13
00:00:53,510 --> 00:00:59,390
And then we are just going to iterate through the cells in this DP array in a length wise manner okay.

14
00:00:59,390 --> 00:01:00,740
And we have done this many times.

15
00:01:00,740 --> 00:01:02,690
So this should be pretty straightforward.

16
00:01:02,690 --> 00:01:08,240
For let L is equal to one l less than equal to n l plus plus.

17
00:01:08,840 --> 00:01:19,850
And then we have for let I is equal to zero I less than equal to n minus l I plus plus and j would be

18
00:01:19,850 --> 00:01:23,420
equal to I plus l minus one.

19
00:01:24,110 --> 00:01:24,650
Okay.

20
00:01:24,650 --> 00:01:28,970
And now we are first going to check whether I is equal to j.

21
00:01:28,970 --> 00:01:33,560
Because if these two are equal we are just having a substring of length one.

22
00:01:33,560 --> 00:01:34,760
And that is a palindrome.

23
00:01:34,760 --> 00:01:41,180
So we can say dp at ij is equal to zero which indicates that because the substring that we are dealing

24
00:01:41,180 --> 00:01:44,390
with is a palindrome, we would just need zero cuts.

25
00:01:44,390 --> 00:01:44,840
Okay.

26
00:01:44,840 --> 00:01:51,740
Now if this is not the case, let's check whether s at I is equal to s at j.

27
00:01:51,740 --> 00:01:59,660
And if these two are equal, and if the substring that we get by removing the ith and jth character,

28
00:01:59,660 --> 00:02:03,710
which can be checked by taking a look at dp at I plus one j minus one.

29
00:02:03,710 --> 00:02:09,260
So if this also is a palindrome and if that is the case this would be equal to zero okay.

30
00:02:09,260 --> 00:02:16,580
So if this is the case then the substring that goes from the ith index till the jth index is also a

31
00:02:16,580 --> 00:02:17,090
palindrome.

32
00:02:17,090 --> 00:02:23,150
And therefore we can say dp at ij is equal to zero, which means again that we would not need any cuts

33
00:02:23,150 --> 00:02:23,870
in this case.

34
00:02:23,870 --> 00:02:34,190
Now if that is not the case, then initially we set dp at ij to be equal to j minus I, which would

35
00:02:34,190 --> 00:02:36,410
be the maximum number of cuts required.

36
00:02:36,410 --> 00:02:36,860
Okay.

37
00:02:36,860 --> 00:02:39,290
And then we are going to use another variable.

38
00:02:39,290 --> 00:02:40,520
Let's say we call it k.

39
00:02:40,520 --> 00:02:47,090
So for k is equal to I k less than j k plus plus.

40
00:02:47,090 --> 00:02:51,380
So k will take the values from I up to j minus one.

41
00:02:51,380 --> 00:02:56,930
And then we are going to say dp at I j is equal to math dot min.

42
00:02:57,500 --> 00:03:10,160
And we will take the minimum value between dp at ij and one plus dp at I k plus dp at k plus one j.

43
00:03:11,140 --> 00:03:11,680
Okay.

44
00:03:11,680 --> 00:03:14,920
And we've discussed the logic for this in detail in the previous video.

45
00:03:14,920 --> 00:03:18,700
So again basically k takes the values from I up to j minus one.

46
00:03:18,700 --> 00:03:25,360
And in such a way we are making partitions and we are trying to see in which partition the number of

47
00:03:25,360 --> 00:03:26,500
cuts is minimum.

48
00:03:26,500 --> 00:03:26,830
Okay.

49
00:03:26,830 --> 00:03:30,400
So that would be the value that is assigned to DP at ij.

50
00:03:30,490 --> 00:03:33,430
And then once we are out of this for loop okay.

51
00:03:33,430 --> 00:03:37,690
Over here we'll just return depee at zero n minus one.

52
00:03:38,320 --> 00:03:40,720
And again notice the entire string.

53
00:03:40,720 --> 00:03:45,100
The string s, which is given to us spans from index zero to n minus one.

54
00:03:45,100 --> 00:03:48,940
So that's why this is actually the original problem which has been given to us.

55
00:03:48,940 --> 00:03:52,480
And therefore we can just return DP at zero n minus one.

56
00:03:52,480 --> 00:03:56,440
And that would give us the minimum cuts required for the entire string.

57
00:03:56,440 --> 00:04:00,580
Now let's go ahead and run this code and see if it's passing all the test cases.

58
00:04:02,150 --> 00:04:03,890
And you can see that it's working.

59
00:04:03,890 --> 00:04:05,600
It's passing all the test cases.

60
00:04:05,600 --> 00:04:09,530
So this is the tabulation approach for solving palindrome partitioning to.

61
00:04:09,530 --> 00:04:11,930
And notice we have used a 2D DP array.