Let's now implement the memoization approach that we have discussed in the previous video for the palindrome
partitioning two question.
And let's also make a change over here.
Earlier when we implemented the recursive solution, we had this function over here to check whether
a particular substring is a palindrome or not.
So let's replace this.
And instead of that, let's implement the tabulation approach where we are going to check only once
whether a particular substring is a palindrome or not.
Okay.
So for this let's have a 2D depee table and let me just call it is palindrome.
And again before that, let me say that the length of the given string is equal to n.
So let n is equal to s dot length okay.
And this dp table.
This 2d dp table will be of size n into n.
So I can say array dot from array n okay.
And we also need n columns.
Now let's go ahead and fill every cell in this particular DP table with the value false.
All right.
Now what we're going to do is we're going to iterate through the cells in this S palindrome DP table
lengthwise.
And wherever we encounter a substring that is a palindrome will fill the value true over there.
And this is something that you have done many times.
So you should be pretty familiar with this by now.
So we can say for let L is equal to one l less than or equal to n l plus plus okay.
Because length takes the values from one up to n and then we have for let I is equal to zero I less
than or equal to n minus l I plus plus okay.
And j is going to equal I plus l minus one.
Now for every combination of I and j we have to evaluate whether we are dealing with the palindrome
or not.
So first we will check if I is equal to j then we can just say is palindrome at I.
J is true because we are just dealing with a string which has one character, okay.
And that is a palindrome.
And if that is not the case, we have to check whether s at I is equal to s at j.
And if these are equal, then either we should be dealing with a string which just has two characters.
And for that we can check whether j is equal to I plus one.
Or we will have to check whether the substring that we get after removing the ith and jth character,
or the substring in between the ith and jth character is a palindrome or not.
And because we are doing this iteration lengthwise, we would have already calculated it previously
and we can just check is palindrome I plus one j minus one.
Okay.
So if this is true it would mean that the substring that you get when you remove the ith and jth character
is also a palindrome.
Now if this is the case, that is, if this is true and if either of these conditions is true, then
this particular substring is a palindrome.
And we can say is palindrome I j is equal to true.
All right.
Now if this is not the case then this particular substring is not a palindrome.
That's it.
Now you can either say is palindrome I j is equal to false.
Or you can just leave it as well because initially we have initialized every cell with the value false.
But I'm just writing it over here for clarity's sake.
So as of now we have iterated lengthwise through the is palindrome table DP table that we have created
over here.
And for every cell that represents a substring that is a palindrome, we have filled the value true
over there.
Now we would need one more DP table.
Let's just call it min cuts okay.
So let's call it min cuts.
And in this table we will store the minimum cuts required for every substring to ensure that it's partitioned
in a way that every partition is a palindrome.
Now this DP table over here, which is min cuts, is also going to have n rows and n columns.
So I can say array dot from array n okay.
And it also needs n columns.
And we will fill every cell in this DP table over here with null okay.
Now let's go ahead and write the main function.
So we have this partitions function over here which we had previously written.
Now we're going to slightly modify this to ensure that this solution is the memoization solution.
So first we have the base case over here where the start is equal to end.
And whether the substring which is given to us is a palindrome or not.
And in which case we return zero.
So there is no change logically in the base case.
But because we have changed the way that we check whether a substring is a palindrome or not.
So we would have to change that, because initially we had a function.
But now we are going to use this particular DP table over here okay.
So I'll say is palindrome at start and end okay.
Now if this is true it would mean that yes, this particular string which is given to us is a palindrome.
So this is the base case.
Now we just had a slight tweak over here.
Now after the base case before we go ahead over here and do these computations, we will first check
whether we had already computed and stored the number of cuts required for this particular substring
at hand.
And for that we will just make use of this dp table min cuts, and we will see whether if min cuts at
start end is not equal to null okay.
We.
Because over here, notice we had filled every cell in this deep table with the value null.
But if we see over here that min cuts at start end is not equal to null.
The reason for this would be that we already previously computed this and we stored it in this particular
table.
Okay.
Now if that is the case then we don't need to recompute it, but rather we will just return min cuts
at start end.
Okay.
Now, if this is not the case, then we proceed.
We have the maximum value assigned to minimum cuts over here.
And then we have this for loop.
We calculate the minimum cuts over here and over here.
Before we return it we are going to store it.
So we can say min cuts at start end is equal to whatever we get over here which is minimum cuts okay.
And then we will just return this.
All right.
So that's it.
So with just a few tweaks we were able to convert the recursive solution to the memoization solution.
And we have also implemented a tabulation approach over here to calculate whether a substring is a palindrome
or not.
And that helps us to improve the time complexity because we are checking whether a particular substring
is a palindrome or not only one type.
Now let's go ahead and run this code and see if it's passing all the test cases.
All right.
So there's an error.
Now again the error is because over here is palindrome.
In the previous implementation it was a function right.
But over here we have changed it to a table.
And I forgot to change this.
So let's change this.
So this should be is palindrome at start and end index.
Okay.
So this should solve it.
Now let's go ahead and again run this 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 memoization approach for solving palindrome partitioning two.