Palindromic String Partition | Variation of MCM

help
,
1

Hey, Guys, I watched Video From Aditya Verma series and then Write Optimise Code for
Palindromic String Partition but it is giving me TLE.
Please check it

Question Link

My solution idone Link

My leetcode solution which is giving TLE

@aneee004 @galencolin @akshitm16 @ssjgz

Please help.

2

I’m not sure why you’re getting TLE. It looks like your code is \mathcal O(n^2). Did you try a bottom up approach?

Here is my \mathcal O(n^2) implementation, but with a 1D dp.

Code 
class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> ispal(n, vector<bool>(n));
        for(int i = 0; i < n; i++) ispal[i][i] = 1;
        for(int i = 1; i < n; i++) ispal[i][i - 1] = 1;
        for(int p = 1; p < n; p++) {
            for(int i = 0; i < n - p; i++) {
                int j = i + p;
                if(s[i] == s[j]) ispal[i][j] = ispal[i + 1][j - 1];
            }
        }
        vector<int> dp(n, INT_MAX);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                if(ispal[j][i]) {
                    if(j == 0)
                        dp[i] = min(dp[i], 0);
                    else
                        dp[i] = min(dp[i], 1 + dp[j - 1]);
                }
            }
        }
        return dp[n-1];
    }
};
2 Likes
3

Actually I don’t understood the bottom up dp for this problem i,e., I decided to solve using top down approach.
I also unable to figure out why its giving me TLE.

4

Argh. I see why. Pass your string by reference and not by value. If you pass it by value, the string is copied for each and every call, which is another \mathcal O(n). So the overall runtime is \mathcal O(n^3).

2 Likes
5

Can you explain me why this coping takes O(N) time complexity.

Actually I tried using call by reference but also giving TLE. What to do now sir!!! :joy: :joy:

6

To copy a string, you have to copy character by character, which is \mathcal O(n).

Try with a global string for the given string? (There isn’t much difference, but I don’t see any other reason for TLE).

1 Like
7

Sorry to disturb but open this brother and see this

8

Um, I don’t think people can see your submission. It says Error 404 when I open it.

1 Like
9

I am sorry brother, But this link is opening in me correctly. one second I bind the code and give it to you.

Leetcode Question Link

Please copy code from here and paste to above leetcode partition Question Page

I have also done by using call by reference still it is giving me a TLE. :pensive: :pensive:

10

Don’t memset all 1500*1500 values for every test case. That’s because sum of n over all test cases might be lesser than than T*1500*1500. I tried changing it but it still give TLE.

@ssjgz, are there any flaws with a top down dp, which increases the runtime? Feels like a state will be accessed 2^n times. But I haven’t really faced/seen problems where that causes an increased runtime.

1 Like