Pretty confused. C++ O(N^2) DP method always get TLE, please give some help.


  • 2
    W

    The main idea is using palindrome[i][j] array stores the information whether s.substr(i, j - i + 1) is a palindrome string, cut[i] array stores the minCut solution of s.substr(i).

    I beg the time complexity is O(N^2), but still can't pass the OJ case aaaaa....aa.

    Finally, I translate the code into java and passed... Can anyone give some help?

    class Solution {
    public:
        int minCut(string s) {
            int N = s.size();
    		if (N == 0) {
    			return 0;
    		}
    		vector<vector<bool> > palindrome(N, vector<bool>(N, false));
    		vector<int> cut(N, 0);
    		for (int start = N - 1; start >= 0; --start) {
    			cut[start] = N - start - 1;
    			for (int end = start; end < N; ++end) {
    				if (s[start] == s[end]) {
    					palindrome[start][end] = (end - start < 2) ? true : palindrome[start + 1][end - 1];
    				}
    				if (palindrome[start][end]) {
    					if (end == N - 1) {
    						cut[start] = 0;
    					}
    					else {
    						cut[start] = min(cut[start], cut[end + 1] + 1);
    					}
    				}
    			}
    		}
    		return cut[0];
        }
    };

  • 0
    B

    My plain C solution also runs in O(N^2) and fails with TLE. It's far better than N^2 for most inputs.

    I've also found that sometimes my code fails with TLE, but if I resubmit the same code, it is accepted. So it appears the time limits are set very close to the minimum feasible execution time.

    All that is to say, the time limits seem to be bogus. Perhaps it is a way to encourage book sales?


  • 0
    Z

    I got the same problem.
    Change

    vector<vector<bool> > palindrome(N, vector<bool>(N, false));
    

    to

    bool palindrome[N][N];
    

    might works.

    But I still don't know why a vector can cause LTE while array can pass easily.

    Can someone help?

    Following is my code. if I use vector it cause LTE. if I use array it passed with 21ms. STRANGE!

    class Solution {
    public:
        int minCut(string s) {
            int l=s.length();
            //vector<vector<bool>> dp(l,vector<bool>(l,1)); 
            bool dp[l][l];
            for(int j=0;j<l;j++){
                for(int i=0;i+j<l;i++)
                    dp[i][i+j]=(j<2||dp[i+1][i+j-1])&&(s[i]==s[i+j]);
            }
            if(dp[0][l-1]) return 0;
            int cut[l];
            cut[0]=0;
            for(int i=1;i<l;i++){
                if(dp[0][i]) cut[i]=0;
                else{
                    cut[i]=l;
                    for(int j=0;j<i;j++)
                        if(dp[j+1][i]&&cut[i]>cut[j]+1) cut[i]=cut[j]+1;
                }
            }
            return cut[l-1];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.