Way based on stack and DP( use look-up table ) in C++ , O(n) space and O(n) time


  • 0
    L
    int longestValidParentheses(string s) {
    if (s.size() <= 1)
    	return 0;
    stack<int> sta;
    vector<int> vec;
    int cur = 0;
    int max = 0;
    for (int i = 0; i != s.size(); i++)
    {
    	if (s[i] == '(')
    	{
    		vec.push_back(0);
    		sta.push(i);
    	}
    
    	else
    	{
    		if (!sta.empty())
    		{
    			int loc = sta.top();
    			sta.pop();
    			cur = i - loc + 1;
    			if (loc > 0 )
    				cur += vec[loc - 1];
    			vec.push_back(cur);
    		}
    		else
    			vec.push_back(0);
    		max = cur > max ? cur : max;
    	}
    }
    return max; }

Log in to reply
 

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