Solution in C++ O(n)


  • 0
    P
    class Solution 
    {
    public:
    	int longestValidParentheses(string s)
    	{
    		int len = s.size(), maxLen = 0;
    		vector<int> iCount(len + 1, 0), leftCount(len + 1, 0);
    		for (int i = 0; i < len; ++i)
    		{
    			if (s[i] == '(') 
    			{ 
    				leftCount[i + 1] = leftCount[i] + 1;
    				iCount[i + 1] = 0;
    			}
    			else 
    			{
    				if (leftCount[i] > 0) 
    				{
    					leftCount[i + 1] = leftCount[i] - 1;
    					if (s[i - 1] == '(') iCount[i + 1] = iCount[i - 1] + 2;
    					else iCount[i + 1] = iCount[i] + 2 + iCount[i - iCount[i] - 1];
    				}
    			}
    			maxLen = maxLen < iCount[i + 1] ? iCount[i + 1] : maxLen;
    		}
    		return maxLen;
    	}
    };

  • 0
    P
    class SolutionB
    {
    public:
    	int longestValidParentheses(string s) 
    	{
    		int len = s.size(), maxLen = 0, validLeft = 0;
    		vector<int> iCount(len, 0);
    		for (int i = 0; i < len; ++i)
    		{
    			if ('(' == s[i]) ++validLeft;
    			else if (validLeft > 0) 
    			{
    				--validLeft;
    				if ('(' == s[i - 1]) iCount[i] = iCount[i - 2] + 2;
    				else iCount[i] = iCount[i - 1] + 2 + iCount[i - 2 - iCount[i - 1]];
    			}
    			maxLen = iCount[i] > maxLen ? iCount[i] : maxLen;
    		}
    		return maxLen;
    	}
    };

Log in to reply
 

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