Welcome back.
Let's now implement the recursive solution for solving palindrome partitioning two.
Okay.
So this solution over here is not going to use dynamic programming.
And we will be needing a function to check whether a particular substring is a palindrome.
So let's just call it a palindrome.
And to this function we will be passing the start and end index.
Okay.
So again basically we will be considering the substring that starts at this particular index and goes
up to this particular index in the given string.
All right.
Now because this function is pretty straightforward let's just go ahead and implement it.
So over here we are going to have a while loop that will keep looping as long as start is less than
end okay.
And over here we are going to check whether s at start is not equal to s at end.
Because if we see that this is true then we can just return false.
But if this is not the case, then we proceed and we are going to move both the pointers okay.
So start will be incremented and end will be decremented.
And that's it.
And again if we come out of the while loop and we are not able to return false, then over here we are
just going to return true.
So this is the function that we will use to check whether a particular substring is a palindrome or
not.
Now let's go ahead and write the main function, which is the function that we will be recursively calling.
Let's just call it partitions.
And to this function.
Also we have to pass the start and end index okay.
And let's write the details of this function later.
And over here we will be calling this function for the first time.
And when we do that we will be passing the first index of string s which is zero, and the last index
of the given string which is s dot length minus one.
All right.
And again we will be writing this function in such a way that we will be getting back the number of
cuts or the minimum number of cuts that we have to make for ensuring that the given string has been
partitioned into palindromes.
And therefore we can just return whatever we get over here.
So this is the skeleton of the solution.
Now let's go ahead and write the details over here.
So we have to write the base case as well as the recursive case over here okay.
Now the base case will be the scenario where either start and end are equal.
Because if that is the case, then the substring that we are considering consists just of one character,
and such a substring is a palindrome.
Or if that is not the case, then we will just check whether the substring that starts at start and
goes up to end is a palindrome, because in either of these two cases, we would not require any cut.
Okay.
So we can say if start is equal to end or is palindrome start comma end.
So if this is true, if either of these is true, then we will just return zero because we would not
require any cut okay.
And again we are making use of this function is palindrome which is what we have written over here.
Now if this is not the case then we proceed with the recursive case.
And again our aim is to identify the minimum number of cuts that we have to do to partition the substring
that starts at start and goes up to end, such that all the partitions are palindromes.
Now to start with, let's have a variable.
Let's just call it minimum cuts.
And this is going to be equal to end minus start.
And again what is it that we are doing over here.
Let me take an example.
Let's say the string which is given to us is a void okay.
So in this case notice that the maximum number of cuts that we need to do to ensure that all the cuts
are palindromes would be three.
Right.
Because if you do a cut over here, a cut over here and a cut over here, then we have ensured that
all the partitions consist of single characters and hence all of them are palindromes.
Okay, so that's why over here we are assigning the maximum possible value which we can get by just
subtracting the start index from the end index.
So we are assigning the maximum possible value to minimum cuts.
And later if we get something lower than that we will replace minimum cuts with the lower value.
So that's the approach that we are taking over here.
Now we are going to have a for loop and we will need a variable.
Let's just call it end index.
And this is going to equal start which is what is given to us over here.
And it will keep going till end minus one okay.
So end index less than end.
And we have end index plus plus okay.
So notice it's going only till end minus one.
And that's because if it were to go up to end then if you are considering a substring that goes from
start up to end index it would be this substring itself.
So that's why we are not taking that okay.
So it will go only up to n minus one.
And now our aim is to see whether we can get a palindrome starting at start and going up to end index.
So we are going to do that check over here.
So if this palindrome start comma end index.
So if we can get a palindrome in this manner then we will go ahead and make a cut over there and recursively
call the partitions function to go deeper down that particular branch in the recursive tree okay.
So if this is true then we will say minimum cuts is equal to math dot min between what we already have
in minimum cuts and the number of cuts that would be required as per this particular partition that
we are going to make over here.
Okay.
So that would be one plus.
Again we are calling the partitions function recursively.
And now we are going to only pass the indices beyond end index.
And that is why the start index in this case would be end index plus one.
And the end index is end itself okay.
So again this over here will give us the number of cut.
Required, as per this particular branch, that we are going deeper and deeper on the recursive tree
to ensure that all the partitions are palindromes.
Okay.
And in this way we will ensure that ultimately minimum cuts will give us the minimum between the various
branches that we can take such that the partitions are palindromes.
And once we are out of this for loop, we would just need to return minimum cuts.
And that's it.
So this should solve the question.
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.