1
00:00:00,790 --> 00:00:07,870
In the previous video, we have discussed the approach which combined both the gap strategy or lengthwise

2
00:00:07,870 --> 00:00:13,240
iteration, as well as backtracking for solving the palindrome partitioning question.

3
00:00:13,390 --> 00:00:16,780
Let's now write the pseudocode for the approach that we discussed.

4
00:00:16,780 --> 00:00:20,920
So initially we would have to build this DP table over here.

5
00:00:20,950 --> 00:00:26,590
Now this is something that we have already done in the palindromic substrings question.

6
00:00:26,590 --> 00:00:29,470
So we'll have to do the same thing over here as well.

7
00:00:29,470 --> 00:00:36,220
And once we are done with that we'll have to write a recursive function for the backtracking over here.

8
00:00:36,220 --> 00:00:38,410
So let's go ahead and write that over here.

9
00:00:38,410 --> 00:00:40,750
Let's call the function partition.

10
00:00:41,050 --> 00:00:43,540
And it will have some inputs over here.

11
00:00:43,540 --> 00:00:46,060
And we are initially calling the function over here.

12
00:00:46,060 --> 00:00:53,170
Now we would have to pass to this function the index that we are considering as well as the current

13
00:00:53,170 --> 00:00:54,970
partition that we are building.

14
00:00:54,970 --> 00:00:57,730
So initially we pass the index zero.

15
00:00:57,730 --> 00:00:59,470
So that's the first index.

16
00:00:59,470 --> 00:01:02,560
And initially the partition is empty.

17
00:01:02,560 --> 00:01:04,960
Now inside the function.

18
00:01:05,540 --> 00:01:09,410
Let's write the base case as well as the recursive case.

19
00:01:09,440 --> 00:01:12,080
Now the base case is pretty straightforward.

20
00:01:12,080 --> 00:01:19,400
When we hit the first invalid input, we would just make a copy of the current partition at hand and

21
00:01:19,400 --> 00:01:20,840
add it to a results array.

22
00:01:20,870 --> 00:01:23,960
So we would need to define a results array over here.

23
00:01:24,260 --> 00:01:32,480
So whenever index is greater than n minus one where n is the length of the input array, we can just

24
00:01:32,480 --> 00:01:36,710
make a copy of cur and append it to this results array.

25
00:01:36,710 --> 00:01:39,590
And finally we will be returning this results array.

26
00:01:39,770 --> 00:01:41,630
So this is the base case.

27
00:01:41,630 --> 00:01:44,360
And let's now write the recursive case.

28
00:01:44,630 --> 00:01:53,060
For the recursive case we would have to evaluate all the possible ways of partitioning starting at this

29
00:01:53,090 --> 00:01:53,750
index.

30
00:01:54,170 --> 00:01:54,650
Okay.

31
00:01:54,650 --> 00:01:59,210
So we can say for I in the range index to n minus one.

32
00:02:01,410 --> 00:02:10,590
We will check whether the substring that starts at index and goes up to I is a palindrome or not, because

33
00:02:10,590 --> 00:02:16,200
if it is a palindrome, it's an indication for us that we can do a partition over there.

34
00:02:16,200 --> 00:02:20,430
So I can say if depee at index I is true.

35
00:02:20,430 --> 00:02:24,840
And over here we are using our DP table, which is what we have built over here.

36
00:02:24,840 --> 00:02:32,580
So if DP at index I is true, then we will append to the current partition that we are building.

37
00:02:32,580 --> 00:02:37,500
The substring that starts at index and goes up to index I.

38
00:02:37,500 --> 00:02:44,070
And then we would recursively call the partition function passing the next index which is I plus one.

39
00:02:44,070 --> 00:02:48,000
And again we are also passing the current partition that we are building.

40
00:02:48,000 --> 00:02:53,910
So to this function call over here the input parameters are I plus one and curr.

41
00:02:53,910 --> 00:02:59,430
And then we would have to do the backtracking step which is to pop the value that we just now added

42
00:02:59,430 --> 00:03:03,030
or appended to the current partition that we were building.

43
00:03:03,330 --> 00:03:04,110
So that's it.

44
00:03:04,110 --> 00:03:07,740
So this is the pseudocode for the approach that we have discussed.

45
00:03:07,770 --> 00:03:12,120
Now remember this part over here where we have a for loop.

46
00:03:12,120 --> 00:03:14,520
And I goes from index to n minus one.

47
00:03:14,520 --> 00:03:19,470
This is used to evaluate all the possible ways of partitioning.

48
00:03:19,470 --> 00:03:25,920
For example initially I is equal to zero because over here we are passing zero index will be equal to

49
00:03:25,920 --> 00:03:30,300
zero and I will have the values from zero up to n minus one.

50
00:03:30,300 --> 00:03:37,920
Now we are going to evaluate the possibilities where I is zero, then one, two etc. up to n minus one.

51
00:03:37,920 --> 00:03:39,570
So that's what we see over here.

52
00:03:39,570 --> 00:03:43,710
So again let me just write the indices over here 012 and three.

53
00:03:43,770 --> 00:03:49,020
When I is equal to zero we are evaluating depee at zero zero.

54
00:03:49,020 --> 00:03:52,710
Index is anyway zero and I is also now zero.

55
00:03:52,710 --> 00:03:58,680
So we are evaluating depee at zero zero which will be this string over here which is a.

56
00:03:58,680 --> 00:04:00,930
And we see that this is a palindrome.

57
00:04:00,930 --> 00:04:06,420
So we go ahead and do these operations over here, which is to append this substring to the current

58
00:04:06,420 --> 00:04:07,620
partition that we are building.

59
00:04:07,620 --> 00:04:13,680
And then make a recursive call to the same function which will again continue building this partition.

60
00:04:13,680 --> 00:04:21,900
Now in the next case, when I is equal to one, we will be evaluating dp zero one, which is this substring

61
00:04:21,900 --> 00:04:22,350
over here.

62
00:04:22,350 --> 00:04:24,540
And again we see that this is true.

63
00:04:24,540 --> 00:04:28,830
And therefore we will make a partition like this which will give us a a.

64
00:04:28,830 --> 00:04:30,330
That's what we're doing over here.

65
00:04:30,330 --> 00:04:34,770
And then we would recursively call the same function to get this part.

66
00:04:34,770 --> 00:04:36,150
And it goes down this way.

67
00:04:36,540 --> 00:04:45,000
So whenever we are seeing that DP at index I is true, we will append the substring that starts at index

68
00:04:45,000 --> 00:04:49,920
and goes up to I to the current partition that we are building.

69
00:04:49,920 --> 00:04:53,520
So again as we discussed this is 0 to 0.

70
00:04:53,520 --> 00:04:56,640
And this over here is 0 to 1.

71
00:04:56,640 --> 00:04:58,170
And it goes on in this manner.

72
00:04:58,170 --> 00:05:03,570
For example, this one over here is 1 to 1 because that's this character.

73
00:05:04,170 --> 00:05:10,230
Which is 1 to 1, because over here, this is the part that was appended to the current partition.

74
00:05:10,230 --> 00:05:15,180
And that's the substring that starts at index one and goes up to index one.

75
00:05:15,210 --> 00:05:20,160
Also let me highlight the backtracking step over here, which is this part.

76
00:05:20,160 --> 00:05:23,610
So we have to pop whatever we appended over here.

77
00:05:23,610 --> 00:05:28,620
And that's required because we are changing the state of the problem in place.

78
00:05:28,620 --> 00:05:33,960
So this is something that you have discussed previously when we discussed backtracking in detail.

79
00:05:33,990 --> 00:05:36,000
Quickly to review that part.

80
00:05:36,030 --> 00:05:40,740
Notice over here we have the current partition as a comma a.

81
00:05:40,740 --> 00:05:45,150
And then when we come to this part we need a comma a b.

82
00:05:45,180 --> 00:05:52,200
So once we are done with this branch when we come back we will pop this a and that will ensure that

83
00:05:52,200 --> 00:05:54,690
the current partition is just a.

84
00:05:54,690 --> 00:05:56,940
And then we can add a, b, a to it.

85
00:05:56,940 --> 00:05:59,160
And therefore we get a comma a b.

86
00:05:59,190 --> 00:06:03,540
So that's why the backtracking step is also very important.

87
00:06:03,540 --> 00:06:04,080
All right.

88
00:06:04,080 --> 00:06:09,360
So we are done writing the pseudo code for the approach that we discussed for solving the palindrome

89
00:06:09,360 --> 00:06:10,530
partitioning question.