1
00:00:00,110 --> 00:00:00,920
Welcome back.

2
00:00:00,920 --> 00:00:05,540
Let's now implement the code for solving the palindrome partitioning question.

3
00:00:05,540 --> 00:00:08,570
So to start with we are given this string over here.

4
00:00:08,570 --> 00:00:12,500
And let's say n is the length of the string okay.

5
00:00:12,500 --> 00:00:18,050
And we will be creating a DP table which will have n rows and n columns.

6
00:00:18,050 --> 00:00:23,060
So I can say array dot from and you have array n over here.

7
00:00:25,820 --> 00:00:29,960
And we will fill every cell in this deep table with false.

8
00:00:31,950 --> 00:00:39,540
Now let's iterate lengthwise through this DB table, and whenever we encounter a substring that spans

9
00:00:39,540 --> 00:00:46,470
from I to J and if it is a palindrome, we will fill true in the DB table, and otherwise we'll have

10
00:00:46,470 --> 00:00:47,160
false over there.

11
00:00:47,190 --> 00:00:49,290
Now this is something that we have done many times.

12
00:00:49,290 --> 00:00:50,850
So let's go ahead and do that.

13
00:00:50,850 --> 00:00:56,340
For let L is equal to one l less than equal to n l plus plus.

14
00:00:56,970 --> 00:01:03,000
Because L takes the values from one up to n, and for every value of L, we'll have another variable

15
00:01:03,000 --> 00:01:03,300
I.

16
00:01:03,330 --> 00:01:11,520
So for let I is equal to zero I less than equal to n minus l I plus plus okay.

17
00:01:11,520 --> 00:01:16,710
And j is going to equal I plus l minus one.

18
00:01:17,070 --> 00:01:21,750
Now first we are going to check whether I and j are equal, which would indicate that we are dealing

19
00:01:21,750 --> 00:01:24,150
with a substring of length one.

20
00:01:24,150 --> 00:01:30,060
So if I is equal to j then we'll say depee at I, j is equal to true.

21
00:01:31,220 --> 00:01:34,820
Because a substring of length one is in fact a palindrome.

22
00:01:34,850 --> 00:01:43,820
Now, if this is not the case, then we will check whether s at I is equal to s at j, and if these

23
00:01:43,820 --> 00:01:53,990
two are equal, then either we should be dealing with a substring of length two or the remaining substring.

24
00:01:53,990 --> 00:01:59,120
After removing the characters at index, I and j should also be a palindrome.

25
00:01:59,150 --> 00:02:02,030
Okay, now again, this is the same thing that we have done previously.

26
00:02:02,030 --> 00:02:03,770
So let's just go and write that.

27
00:02:03,770 --> 00:02:06,230
So DP at I plus one j minus one.

28
00:02:06,230 --> 00:02:10,880
If this is a palindrome, or if you are dealing with a string which just has two characters.

29
00:02:10,880 --> 00:02:17,480
So if either of these is true, and if s at I and j are equal, then we can say dp at I j.

30
00:02:18,920 --> 00:02:20,120
Is equal to true.

31
00:02:20,270 --> 00:02:26,270
And if that is not the case, then dp ij would just be false.

32
00:02:27,550 --> 00:02:34,570
So we have filled this deep table and wherever we have a substring which is a palindrome, we have true

33
00:02:34,570 --> 00:02:35,740
in this deep table.

34
00:02:35,770 --> 00:02:43,030
Now let's go ahead and implement the backtracking part of this solution to identify all the possible

35
00:02:43,030 --> 00:02:44,440
palindromic partitionings.

36
00:02:44,470 --> 00:02:44,890
Okay.

37
00:02:44,890 --> 00:02:47,770
And for this we will be needing a helper function.

38
00:02:47,770 --> 00:02:53,680
And to this helper function we will be passing the index, which is to iterate through the characters

39
00:02:53,680 --> 00:02:54,760
in the input string.

40
00:02:54,760 --> 00:02:56,590
And we will also need an array.

41
00:02:56,590 --> 00:03:00,550
Let's just call it current which will be the partitioning that we are building.

42
00:03:00,550 --> 00:03:02,710
Okay, so we will be just going deeper and deeper.

43
00:03:02,710 --> 00:03:04,720
And we need this array to store it.

44
00:03:04,720 --> 00:03:10,210
And again we are going to make changes to this in place because this is going to be a backtracking approach.

45
00:03:10,210 --> 00:03:13,960
And once we have written this helper function, we will have to call it.

46
00:03:13,960 --> 00:03:17,590
So initially when we call this function we will pass the index zero.

47
00:03:17,590 --> 00:03:20,230
And current at this point will just be an empty array.

48
00:03:20,230 --> 00:03:22,360
And we will also need a variable.

49
00:03:22,360 --> 00:03:26,410
Let's just call it rest to store all the partitionings.

50
00:03:26,410 --> 00:03:31,840
So whenever we get a valid palindromic partitioning will push it to this results array.

51
00:03:31,840 --> 00:03:35,230
And finally we will just return the results array.

52
00:03:35,350 --> 00:03:37,540
So this is the skeleton of this approach.

53
00:03:37,540 --> 00:03:40,330
Now let's just go ahead and complete the helper function.

54
00:03:40,330 --> 00:03:46,270
So over here I will be writing the base case as well as the recursive case okay.

55
00:03:46,270 --> 00:03:53,140
Now the base case would be in this case when we encounter the first invalid index okay that's this index

56
00:03:53,140 --> 00:03:53,590
over here.

57
00:03:53,590 --> 00:03:58,450
So the first invalid index would be if index is greater than n minus one.

58
00:03:58,450 --> 00:04:06,430
So we can say if index greater than n minus one then we will just make a copy of the current state of

59
00:04:06,430 --> 00:04:09,160
current and push it to the results array.

60
00:04:09,160 --> 00:04:13,630
So I can say rest or push array dot from current.

61
00:04:13,630 --> 00:04:13,930
Okay.

62
00:04:13,930 --> 00:04:18,550
So we have made a copy of the current array and we have pushed it to the results array.

63
00:04:18,550 --> 00:04:20,440
And we can just return over here.

64
00:04:21,370 --> 00:04:21,820
All right.

65
00:04:21,820 --> 00:04:28,120
Now, if this is not the case, then we move on to the recursive case and we will need a variable.

66
00:04:28,120 --> 00:04:36,340
Let's just call it I for let I is equal to index and I less than n I plus plus okay.

67
00:04:36,340 --> 00:04:42,340
So I takes the values from index up to the last valid index in the input string okay.

68
00:04:42,340 --> 00:04:46,690
Now over here we are going to check whether depee at index I.

69
00:04:47,170 --> 00:04:52,030
That is the substring that starts at this particular index and goes up to I.

70
00:04:52,060 --> 00:04:57,850
Now if this is a palindrome we would have true in the DP table at this particular cell.

71
00:04:57,850 --> 00:05:03,070
So if dp index I is true we have found a palindromic substring.

72
00:05:03,070 --> 00:05:05,830
And in this case we would make a partitioning over there.

73
00:05:05,830 --> 00:05:13,510
So we can say current dot push s dot substring index comma I plus one okay.

74
00:05:13,510 --> 00:05:20,050
So we are making a partitioning and we are pushing the substring that goes from index up to I to the

75
00:05:20,050 --> 00:05:20,650
current array.

76
00:05:20,650 --> 00:05:25,930
And after we are done with this we will recursively call the helper function again and we will pass

77
00:05:25,930 --> 00:05:28,330
the index as I plus one.

78
00:05:28,330 --> 00:05:30,610
And we will also pass the current array to it.

79
00:05:30,610 --> 00:05:30,970
Okay.

80
00:05:30,970 --> 00:05:33,940
So we are going deeper down that recursive branch.

81
00:05:33,940 --> 00:05:40,630
And once we come back over here we have to do the backtracking step which is current dot pop okay.

82
00:05:41,050 --> 00:05:42,700
So this is the backtracking step.

83
00:05:43,720 --> 00:05:48,280
Now this is required to explore all the branches in the recursive tree okay.

84
00:05:48,280 --> 00:05:52,810
Now let's go ahead and run this code and see if it's passing all the test cases.

85
00:05:54,730 --> 00:05:56,410
And you can see that it's working.

86
00:05:56,410 --> 00:05:58,150
It's passing all the test cases.

87
00:05:58,150 --> 00:06:03,250
So this is the approach that we can take to solve the palindromic partitioning question.

88
00:06:03,250 --> 00:06:07,870
Now notice that over here we have used length wise iteration or the gap strategy.

89
00:06:07,870 --> 00:06:12,280
And we have also made use of backtracking to come up with the solution.