share my truly O(n) DP solution with detailed annotation (4ms)


  • 1
           private static int longestValidParentheses(String s) {
    		int len_s = s.length();
    		if (len_s == 0) return 0;
    		int[] f = new int[len_s];
    		//f[n] means the longestValidParentheses substring ending at n 
    		f[0] = 0;
    		int max = 0;
    		for (int i=0;i<len_s-1;i++) {
    			if (s.charAt(i+1)=='(') {
    				// if the end of substring is '(', it cant be a valid string
    				f[i+1] = 0;
    				continue;
    			}
    			// s.charAt(i+1) == ')'
    			// you get ')' at i+1 so check for the '(' on the left.
    			if (i-f[i]>=0 && s.charAt(i-f[i])=='(') {
    				f[i+1] = 2 + f[i]; 
    				//2 means the '(' at i-f[i] and ')' at i+1,
    				if (i-f[i]-1>=0)
    					f[i+1] += f[i-f[i]-1];
    			}
    			if (f[i+1]>max) max = f[i+1];
    		}
    		return max;
    	}

  • 0
    B

    DP is great!


Log in to reply
 

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