In the previous video, we have discussed the approach which combined both the gap strategy or lengthwise
iteration, as well as backtracking for solving the palindrome partitioning question.
Let's now write the pseudocode for the approach that we discussed.
So initially we would have to build this DP table over here.
Now this is something that we have already done in the palindromic substrings question.
So we'll have to do the same thing over here as well.
And once we are done with that we'll have to write a recursive function for the backtracking over here.
So let's go ahead and write that over here.
Let's call the function partition.
And it will have some inputs over here.
And we are initially calling the function over here.
Now we would have to pass to this function the index that we are considering as well as the current
partition that we are building.
So initially we pass the index zero.
So that's the first index.
And initially the partition is empty.
Now inside the function.
Let's write the base case as well as the recursive case.
Now the base case is pretty straightforward.
When we hit the first invalid input, we would just make a copy of the current partition at hand and
add it to a results array.
So we would need to define a results array over here.
So whenever index is greater than n minus one where n is the length of the input array, we can just
make a copy of cur and append it to this results array.
And finally we will be returning this results array.
So this is the base case.
And let's now write the recursive case.
For the recursive case we would have to evaluate all the possible ways of partitioning starting at this
index.
Okay.
So we can say for I in the range index to n minus one.
We will check whether the substring that starts at index and goes up to I is a palindrome or not, because
if it is a palindrome, it's an indication for us that we can do a partition over there.
So I can say if depee at index I is true.
And over here we are using our DP table, which is what we have built over here.
So if DP at index I is true, then we will append to the current partition that we are building.
The substring that starts at index and goes up to index I.
And then we would recursively call the partition function passing the next index which is I plus one.
And again we are also passing the current partition that we are building.
So to this function call over here the input parameters are I plus one and curr.
And then we would have to do the backtracking step which is to pop the value that we just now added
or appended to the current partition that we were building.
So that's it.
So this is the pseudocode for the approach that we have discussed.
Now remember this part over here where we have a for loop.
And I goes from index to n minus one.
This is used to evaluate all the possible ways of partitioning.
For example initially I is equal to zero because over here we are passing zero index will be equal to
zero and I will have the values from zero up to n minus one.
Now we are going to evaluate the possibilities where I is zero, then one, two etc. up to n minus one.
So that's what we see over here.
So again let me just write the indices over here 012 and three.
When I is equal to zero we are evaluating depee at zero zero.
Index is anyway zero and I is also now zero.
So we are evaluating depee at zero zero which will be this string over here which is a.
And we see that this is a palindrome.
So we go ahead and do these operations over here, which is to append this substring to the current
partition that we are building.
And then make a recursive call to the same function which will again continue building this partition.
Now in the next case, when I is equal to one, we will be evaluating dp zero one, which is this substring
over here.
And again we see that this is true.
And therefore we will make a partition like this which will give us a a.
That's what we're doing over here.
And then we would recursively call the same function to get this part.
And it goes down this way.
So whenever we are seeing that DP at index I is true, we will append the substring that starts at index
and goes up to I to the current partition that we are building.
So again as we discussed this is 0 to 0.
And this over here is 0 to 1.
And it goes on in this manner.
For example, this one over here is 1 to 1 because that's this character.
Which is 1 to 1, because over here, this is the part that was appended to the current partition.
And that's the substring that starts at index one and goes up to index one.
Also let me highlight the backtracking step over here, which is this part.
So we have to pop whatever we appended over here.
And that's required because we are changing the state of the problem in place.
So this is something that you have discussed previously when we discussed backtracking in detail.
Quickly to review that part.
Notice over here we have the current partition as a comma a.
And then when we come to this part we need a comma a b.
So once we are done with this branch when we come back we will pop this a and that will ensure that
the current partition is just a.
And then we can add a, b, a to it.
And therefore we get a comma a b.
So that's why the backtracking step is also very important.
All right.
So we are done writing the pseudo code for the approach that we discussed for solving the palindrome
partitioning question.