Welcome back.
Let's now implement the code for the tabulation approach where we are just using a one dimensional DP
array.
Okay.
So over here I've written this code already which is something that we have written multiple times.
And over here we have this ace palindrome DP table which is an n into n table.
And in this DP table we have stored whether every substring is a palindrome or not okay.
So I'm not going to again revisit this because we have already done this multiple number of times.
But let's now proceed with the remaining part.
So we are going to have a DP table which is just going to be a one dimensional array.
And this array will be of size n, where n is the size of the input string which is given to us.
And we will fill every cell in this DP table with the value zero.
Okay.
Now what we are going to do is we are going to have a variable.
And using that variable we will iterate over every index in this particular DP table.
Now let me quickly pull up my pen.
So let's say this is the input array which is a b a c.
So over here we have created this particular DP table.
Now I'm going to use this end variable.
And end will take the values from zero up to n minus one.
And for each value of end okay I will have another for loop where the start variable will go from zero
to end, and I will keep checking whether the substring that starts at start and goes up to end is a
palindrome or not.
Okay, and using this I will be able to find the minimum cuts required.
Okay.
So in this DP table over here at every cell, I will be filling the number of cuts or the minimum number
of cuts required for the substring that goes from zero up to that particular index.
For example, over here I will be filling the minimum cuts required for this substring over here.
Similarly, over here I will be filling the minimum number of cuts required for the complete substring.
And that's why this is the cell that ultimately we will be returning.
Now quickly reviewing what we have discussed in the previous video.
Now let's say we have a string which is like b c a.
And we see that this over here is a palindrome where start is over here and end is over here.
Okay.
So if this is the case then the minimum number of cuts required would be one which is this cut over
here plus zero because this over here is a palindrome.
Plus whatever the number of cuts are required for this particular substring.
And this would be something that we have already solved.
Okay.
So if this is start this over here would be obtained by Depee at start minus one.
Because we have discussed that over here in this DP table, at every cell, we are going to fill the
number of cuts that are required for the substring that goes from zero up to that particular index.
Okay.
So this index over here is start minus one.
And that's why DP at start minus one will give us the number of cuts required for this substring.
And then we have one cut over here that is plus one.
And over here because we have identified a palindrome we just need zero cuts.
So this is the approach that we are going to take.
Now let's go ahead and implement this.
So we can say for let end is equal to zero and n less than n n plus plus.
Okay.
Because as we have discussed, n will take all the indices of the DP array and for each value of end
first we will have to set min cuts as the maximum possible number of cuts required, which would be
end itself.
Okay.
For example, let's say in this example over here, we are over here where n is equal to two.
Now in this case the maximum number of cuts would be two.
Right.
Why is that the case.
Because over here we would have to make one cut.
And then you would have to make one cut over here.
And all of these are now single character strings and they are all palindromes.
So that's why the maximum number of cuts is given by n itself.
Okay.
So that's why we can say min cuts is equal to n over here.
And after this we are going to see whether we can identify a value lower than this okay.
And for this we will have another loop.
So let's say for let start is equal to zero and start less than or equal to end start plus plus okay.
Now over here we have to keep moving.
Start till we get a scenario where the substring that goes from start to end is a palindrome.
So I can say if is palindrome start end.
So if we get this type of a scenario then first we will check whether start is equal to zero.
Because if start is equal to zero, then the entire substring is a palindrome.
And therefore we would not require any cuts.
So in that case min cuts can be made zero.
But if that is not the case okay.
So let's just move this a little bit up.
So if this is not the case.
So let's have an else over here.
So if this is not the case then min cuts will be the minimum between what we have already in min cuts
and one plus DP at start minus one okay.
And we have discussed why this is the case in detail okay.
So this would be the minimum cuts required.
And then once we are out of this for loop over here that is over here we will just say DP at end because
this has been done for a particular value of n right.
Which is what we get over here.
So we can just say dp at end is equal to min cuts.
That's it.
And then once we are out of this for loop we will just have to return dp at n minus one.
Right.
Because we have discussed at every index in the DP array, we are going to store the minimum number
of cuts required for the substring that spans from zero up to that particular index and dp at n minus
one.
In this regard, would have the minimum number of cuts required for the complete string, right?
The minimum cuts required for the entire string.
So that is the answer to the question which has been asked to us.
And therefore we return this.
So this is the tabulation approach for solving palindrome partitioning to by just using a one dimensional
DP array.
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.