Welcome back.
Let's now implement the tabulation approach for solving palindrome partitioning two.
And over here we will be implementing the approach using a 2D array.
And later we will take a look at the approach which can be taken just using a 1D array.
All right.
So to start with let's say n is the length of the string which is given to us okay.
And we are going to create a DP array which is going to be a 2D array which will have n rows and n columns.
So let's say let dp is equal to array dot from and then you have array n over here.
And we need array and over here as well okay.
So we have created a 2D dp array which has n rows and n columns.
And what we are going to do over here is that we will fill every cell with the value zero okay.
So this is our 2D array.
And then we are just going to iterate through the cells in this DP array in a length wise manner okay.
And we have done this many times.
So this should be pretty straightforward.
For let L is equal to one l less than equal to n l plus plus.
And then we have for let I is equal to zero I less than equal to n minus l I plus plus and j would be
equal to I plus l minus one.
Okay.
And now we are first going to check whether I is equal to j.
Because if these two are equal we are just having a substring of length one.
And that is a palindrome.
So we can say dp at ij is equal to zero which indicates that because the substring that we are dealing
with is a palindrome, we would just need zero cuts.
Okay.
Now if this is not the case, let's check whether s at I is equal to s at j.
And if these two are equal, and if the substring that we get by removing the ith and jth character,
which can be checked by taking a look at dp at I plus one j minus one.
So if this also is a palindrome and if that is the case this would be equal to zero okay.
So if this is the case then the substring that goes from the ith index till the jth index is also a
palindrome.
And therefore we can say dp at ij is equal to zero, which means again that we would not need any cuts
in this case.
Now if that is not the case, then initially we set dp at ij to be equal to j minus I, which would
be the maximum number of cuts required.
Okay.
And then we are going to use another variable.
Let's say we call it k.
So for k is equal to I k less than j k plus plus.
So k will take the values from I up to j minus one.
And then we are going to say dp at I j is equal to math dot min.
And we will take the minimum value between dp at ij and one plus dp at I k plus dp at k plus one j.
Okay.
And we've discussed the logic for this in detail in the previous video.
So again basically k takes the values from I up to j minus one.
And in such a way we are making partitions and we are trying to see in which partition the number of
cuts is minimum.
Okay.
So that would be the value that is assigned to DP at ij.
And then once we are out of this for loop okay.
Over here we'll just return depee at zero n minus one.
And again notice the entire string.
The string s, which is given to us spans from index zero to n minus one.
So that's why this is actually the original problem which has been given to us.
And therefore we can just return DP at zero n minus one.
And that would give us the minimum cuts required for the entire string.
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 tabulation approach for solving palindrome partitioning to.
And notice we have used a 2D DP array.