Welcome back.
Let's now implement the code for solving the palindrome partitioning question.
So to start with we are given this string over here.
And let's say n is the length of the string okay.
And we will be creating a DP table which will have n rows and n columns.
So I can say array dot from and you have array n over here.
And we will fill every cell in this deep table with false.
Now let's iterate lengthwise through this DB table, and whenever we encounter a substring that spans
from I to J and if it is a palindrome, we will fill true in the DB table, and otherwise we'll have
false over there.
Now this is something that we have done many times.
So let's go ahead and do that.
For let L is equal to one l less than equal to n l plus plus.
Because L takes the values from one up to n, and for every value of L, we'll have another variable
I.
So for let I is equal to zero I less than equal to n minus l I plus plus okay.
And j is going to equal I plus l minus one.
Now first we are going to check whether I and j are equal, which would indicate that we are dealing
with a substring of length one.
So if I is equal to j then we'll say depee at I, j is equal to true.
Because a substring of length one is in fact a palindrome.
Now, if this is not the case, then we will check whether s at I is equal to s at j, and if these
two are equal, then either we should be dealing with a substring of length two or the remaining substring.
After removing the characters at index, I and j should also be a palindrome.
Okay, now again, this is the same thing that we have done previously.
So let's just go and write that.
So DP at I plus one j minus one.
If this is a palindrome, or if you are dealing with a string which just has two characters.
So if either of these is true, and if s at I and j are equal, then we can say dp at I j.
Is equal to true.
And if that is not the case, then dp ij would just be false.
So we have filled this deep table and wherever we have a substring which is a palindrome, we have true
in this deep table.
Now let's go ahead and implement the backtracking part of this solution to identify all the possible
palindromic partitionings.
Okay.
And for this we will be needing a helper function.
And to this helper function we will be passing the index, which is to iterate through the characters
in the input string.
And we will also need an array.
Let's just call it current which will be the partitioning that we are building.
Okay, so we will be just going deeper and deeper.
And we need this array to store it.
And again we are going to make changes to this in place because this is going to be a backtracking approach.
And once we have written this helper function, we will have to call it.
So initially when we call this function we will pass the index zero.
And current at this point will just be an empty array.
And we will also need a variable.
Let's just call it rest to store all the partitionings.
So whenever we get a valid palindromic partitioning will push it to this results array.
And finally we will just return the results array.
So this is the skeleton of this approach.
Now let's just go ahead and complete the helper function.
So over here I will be writing the base case as well as the recursive case okay.
Now the base case would be in this case when we encounter the first invalid index okay that's this index
over here.
So the first invalid index would be if index is greater than n minus one.
So we can say if index greater than n minus one then we will just make a copy of the current state of
current and push it to the results array.
So I can say rest or push array dot from current.
Okay.
So we have made a copy of the current array and we have pushed it to the results array.
And we can just return over here.
All right.
Now, if this is not the case, then we move on to the recursive case and we will need a variable.
Let's just call it I for let I is equal to index and I less than n I plus plus okay.
So I takes the values from index up to the last valid index in the input string okay.
Now over here we are going to check whether depee at index I.
That is the substring that starts at this particular index and goes up to I.
Now if this is a palindrome we would have true in the DP table at this particular cell.
So if dp index I is true we have found a palindromic substring.
And in this case we would make a partitioning over there.
So we can say current dot push s dot substring index comma I plus one okay.
So we are making a partitioning and we are pushing the substring that goes from index up to I to the
current array.
And after we are done with this we will recursively call the helper function again and we will pass
the index as I plus one.
And we will also pass the current array to it.
Okay.
So we are going deeper down that recursive branch.
And once we come back over here we have to do the backtracking step which is current dot pop okay.
So this is the backtracking step.
Now this is required to explore all the branches in the recursive tree okay.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's working.
It's passing all the test cases.
So this is the approach that we can take to solve the palindromic partitioning question.
Now notice that over here we have used length wise iteration or the gap strategy.
And we have also made use of backtracking to come up with the solution.