Hey there and welcome back now for solving the palindrome Partitioning two question.
We will take a look at these three approaches.
First we will take a look at the recursion approach.
Then we will memorize it.
And then we will discuss the tabulation approach for solving this question.
And when we discuss the tabulation approach we will try to solve this question both using a 2D DP array
as well as using a one dimensional array.
So let's get started with the recursion approach.
So for this let's say the input which is given to us is a b a c.
Now let's try to draw the recursion tree for this input.
The way that we are going to approach this is we are going to see where we can make a partition such
that the string that we are going to get on the left side after making a partition is in fact a palindrome.
For example, notice that we could make a partition over here, and then over here we are getting a
palindrome.
Right.
So this is a possibility.
So if you are doing this then the subproblem that remains would be this string over here which is b
a a c.
And we will have to add one to it because we are making a partition over here in a similar manner.
We could also have done the partition over here because a, b, a is a palindrome.
And if we do that, then the problem that remains is a C.
And the solution would be one plus the number of partitions required for a C.
And we are doing one plus over here because we have done a partition over here.
So there are these two possibilities.
And again the approach is that we will be iterating over the characters from left to right.
And we are going to explore whether we can make a partition and we can make a partition.
If we see that the string on the left hand side will be a palindrome, which is the case over here and
the case over here.
So that's why we are getting only two possibilities over here.
And finally we would have to return the minimum among these two solutions.
So this over here will finally give us a number or the number of partitions required.
And this also will give us a number.
And because we are asked to identify the minimum number of cuts required, we would have to identify
the minimum between these two and return that value.
Now let's go down this branch over here.
Now remember we are only dealing with this subproblem over here which is b a, a c.
Again we are going to go from left to right.
And our aim is to identify the places where we can make a cut such that the string to the left of it
is a palindrome.
Now, for example, we could make a cut over here and if we do that, this subproblem over here will
change to one plus a, a, c because this is the remaining string.
And then we have to do one plus over here because we have done a cut over here.
Also notice that there is no other place where we could do a cut such that the string on the left hand
side will become a palindrome.
So this over here will have only one branch, and then we can go further down to solve this subproblem
over here, which is the string a, a c.
Now over here again we move from left to right.
And we are trying to identify positions where we can make cuts such that the string to the left is a
palindrome.
And we see that we could do a cut over here as well as a cut over here.
So the two ways in which this can be partitioned is one plus a C and one plus c one plus a C.
Because if you do the cut over here this is the remaining string.
And then if you do the cut over here we just have C left.
So these are the two branches that this will have.
And then finally we would be returning the minimum among these two for finding the answer for this problem
a c.
And over here we have already reached the end of this branch because we just have one more character
over here and over here a C for solving a C, we can again make one more cut and we would get one plus
C.
Let's also complete this branch over here because we have one plus AC to solve AC.
We would need one more cut and this becomes one plus C.
So this is how the recursion tree would look like for this problem.
And notice that we are actually following a backtracking approach over here.
Or more technically, a pruned recursion approach.
Now I'm calling this pruned recursion because notice that we are pruning branches that don't lead to
a solution.
For example, over here, having a cut at this place would not lead to a solution because this is not
a palindrome.
So the branch one plus A, a c was pruned because this is not a viable solution.
So that's why this is a pruned recursive approach.
And again we are not calling it strictly backtracking because we are not making changes to the state
of the problem.
What we are doing is just we are using pointers to go down the branches of the recursion tree.
So this is a pruned recursive approach.
And the time complexity of this approach is going to be of the order of n into two to the power n.
Now why is that so?
First of all, previously we have discussed that if we are given a string of length n, then the number
of partitions that we can have for this string would be two to the power n minus one.
So I'm not going to repeat it over here.
We have already discussed this in a previous video.
So the number of partitions is going to equal two to the power n minus one.
And we can say that this value over here is of the order of two to the power n.
Now let's make some space over here.
So we have seen that the number of partitions is of the order of two to the power n, and for each of
these partitions we'll have to do palindrome checks on various substrings.
Now for each partition, this part over here, that is the various palindrome checks that we'll have
to do for various substrings.
This together for a partition will require work of the order of n, because n is the length of the string
which is given to us, and because we'll have to do this much work for each partition, and because
we have two to the power n partitions.
The total time complexity of this approach is of the order of n into two to the power n.