I tried all kinds of optimization, but it also TLE..could anybody help me ?


  • 0
    R
    int longestValidParentheses(string str)
    {
    	int n=str.size();
    	if(n==0) return 0;
    	
    	bool** dp=new bool*[n];
    	for(int i=0;i<n;i++)
    		dp[i]=new bool[n];
    	/*
    		for(int i=0;i<str.size();i++)
    		{
    			for(int j=0;j<str.size();j++)
    			{
    				cout<<dp[i][j]<<" ";
    			}
    			cout<<endl;
    		}*/
    	
    	for(int i=0;i<=n-1;i++)
    		dp[i][i]=false;
    	int maxlen=0;
    	for(int i=0;i<=n-2;i++)
    	{
    		if(str[i]=='(' && str[i+1]==')')
    			dp[i][i+1]=true,maxlen=2;
    		else 
    			dp[i][i+1]=false;
    	}
    	for(int length=3;length<=n;length++)
    	{
    		for(int i=0;i<=n-3;i++)
    		{
    			int j=i+length-1;
    			if(j>=n)
    				break;
    			dp[i][j]=false;
    			if(dp[i+1][j-1]==true && str[i]=='(' && str[j]==')')
    			{	dp[i][j]=true; maxlen=length;continue;}
    			for(int k=i;k<j;k++)
    			{
    				if(dp[i][k] && dp[k+1][j])
    				{	dp[i][j]=true;maxlen=length;break;}
    			}
    		}
    	}
    	
    	for(int i=0;i<n;i++)
    		delete[] dp[i];
    	delete[] dp;
    	
    	return maxlen;
    }
    

    I use three loop to get the best result, I think it's needed, but it TLE, in my local machine, costs 1078ms, for a very long string, also I find that global variables would be slower than heap, why? Also bool heap initialized with unexpected value.... This a dp solution, before I use stack to process it for one pass, but tried to modify logic codes for thousands of times, then I find it it was DP, my tears.......

    Could anybody help me?


  • 0
    S

    This problem is expected to be solved in O(n). There is actually a quite simple one-pass linear solution using a stack: When encountering a '(', you always push its position to the stack; when encountering a ')', you pop one element out of the stack (the position of the '(' that matches the current ')' ), and now the top element (if there is one) after .pop() is the "position of the '(' that immediately precedes the longest valid sequence the ends at the current ')' ". If the stack becomes empty() at any point, then special handling must be taken. The logic seems hard to describe; see if you can understand the following accepted code:

    int longestValidParentheses(string s) {
        if (s.empty()) return 0;
        stack<int> ms;
        int maxlen = 0;
        int last = -1;  // Position of the last unmatched ')'
        for (int i = 0; i < s.size(); i ++)
        {
            if (s[i] == '(') ms.push(i); // 
            else if (ms.empty()) last = i; // == ')' and the stack is empty, it means this is a non-matching ')'
            else
            {
                ms.pop();           // pops the matching '('.
                if (ms.empty()) // If there is nothing left in the stack, it means this ')' matches a '(' after the last unmatched ')'
                    maxlen = max(maxlen, i-last);
                else    // otherwise, 
                    maxlen = max(maxlen, i-ms.top());
            }
        }
        return maxlen;
    }

  • 0
    R

    This algorithm seems a brainstorm method. stack stores position, which I have not thought before, it is so hard to think. maxlen records current longest string length, last records last unmatched ), by the way, is it a greedy algorithm? I think greedy algorithm seems hard to think, definitely......Do you have some suggestions for me to improve my algorithm ability? Thanks


Log in to reply
 

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