My C++ 8ms O(n) space solution


  • 0
    A

    Well, the actual code is not long but I added the comments to illustrated the logics. The basic idea is to use a table to record maxlen of valid parentheses ending in every position, and keep filling the table with previous values.

    int longestValidParentheses(string s) {
    	// t as a table, the i-th element represent the length of 
    	// longest valid parentheses ending at position i
    	vector<int> t(s.size(),0); 
    	int sz = s.size();
    	int mt = 0;
    	for (int i = 0;i < sz;i++) {
    		if (s[i] == ')' && i - 1 >= 0) {
    			if (s[i - 1] == '(') {
    				t[i] = 2;
    				if (i - t[i] >= 0) {
    					t[i] += t[i - t[i]];
    				}
    			}
    			else if(t[i-1]!=0 && i-1-t[i-1]>=0 && s[i-1-t[i-1]]=='(') {  
    				t[i] = t[i-1] + 2;
    				if (i - t[i] >= 0 && t[i - t[i]]) {
    					// tracing back to merge previous valid length if 
    					// they are continuous with present one
    					// s| ()(())		s| ()(())
    					// t| 020024   =>   t| 020026
    					//     |___|
    					// we need this look-up because the  increment of t[i] is
    					// made by left corresponding '('.Let's assume the '(' as in
    					// position j, then t[j] is 0 and give us no infomation about the
    					// parentheses lenth before it.
    					t[i] += t[i - t[i]];
    				}
    			}
    			mt = max(mt, t[i]);
    		}
    	}
    	return mt;
    }

Log in to reply
 

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