Previously, we have discussed the tabulation or bottom up approach for solving palindrome partitioning
two by just using a one dimensional array.
Now let's go ahead and take a look at the space and time complexity of the approach that we have discussed.
So the time complexity for this part, which is to build a 2D array called is palindrome will be of
the order of n square.
And we have discussed this multiple times previously, so we're not going to repeat it over here.
Now let's take a look at this part of the pseudocode.
Now this part over here will almost do n iterations.
And this part over here will also do n iterations in the worst case.
So these two together will have a time complexity of the order of n into n.
And then the operations over here are just constant time operations, because checking whether the string
that goes from start to end is a palindrome is going to be a constant time operation, because we're
just going to use this DP table over here, which is something that we've already pre-computed.
And then we just have to identify the minimum between a set of values.
So that's why the total time complexity of this approach is going to be of the order of N square.
Now what about the space complexity?
The space complexity of this solution is also going to be of the order of n square, because we have
to construct this 2D dp array for checking whether a substring is a palindrome or not.
Now this part over here takes up space only of the order of n.
Therefore, the total space complexity of the solution is going to be of the order of n square.