Share my 10-ms solution, in C++ with complexity of O(n), using dynamic programing


  • 0
    E
    int longestValidParentheses(string s) {
    		int *f;
    		int len = s.size();
    		if (len <= 1) {
    			return 0;
    		}
    		f = new int[len];
    		f[0] = 0;
    		int last = 0;						// last char to match
    		int max = 0;
    		for (int i = 1; i < len; ++i) 
    		{
    			f[i] = 0;
    			last = i - f[i - 1] - 1;		//  exp: "()(())", i = 5, f[4] = 2, last = 2;
    			if (last >= 0 && s[i] == ')' && s[last] == '('){	// if it's valid 
    				f[i] = f[i-1] + 2;								// update f[i]
    				if (last - 1 > 0) {								// before the current valid string
    					f[i] += f[last-1];							// if it is valid, increase the f[i]
    				}
    				if (f[i] > max) {								// update max
    					max = f[i];
    				}
    			}
    		}
    		return max;
    	}

  • 0
    B

    You newed an array, and didn't delete it.


Log in to reply
 

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