DP code with no ugly conditions check!!


  • 0
    K

    Well, you know the rule. Just quick recap here.
    Looping through every character of string, checking only the ')', because '(' is not a valid end.
    Two things could happen here,

    1. if previous character = '(', we need to update dp[], so dp[i] = dp[i-2] + 2;
      a. i.e. i = 3 here, "()()", dp[3] = dp[1] + 2, since dp[1] = 2, so dp[3] = 2 + 2 = 4.
      b. i.e. i = 3 here, "))()", dp[3] = dp[1] + 2, since dp[1] = 0, so dp[3] = 0 + 2 = 2.
    2. else previous character = ')', then we have to check the character before the last valid expression which is at i - dp[i-1] - 1, if that is = '(', we have to update, dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2
      a. i.e. i = 5 here, "()(())", dp[5] = dp[1] + dp[4] + 2, since dp[1] = 2 & dp[4] = 2, so dp[5] = 2 + 2 + 2 = 6.
      a. i.e. i = 5 here, "))(())", dp[5] = dp[1] + dp[4] + 2, since dp[1] = 0 & dp[4] = 2, so dp[5] = 0 + 2 + 2 = 4.

    One may ask how do we resolve the corner case, such as "()" or "))" ? There is no i-2 = -1 character here.
    Well, just like linkedlist, we can add a dummy character in the beginning.
    I used 'x' here, but if you feel like you have to conform the rule that string only contains '(' and ')', you can use ')'. :)
    This makes the code extra clean.

    public static int longestValidParentheses(String s) {
    	if (s == null) return 0;
    	int[] dp = new int[s.length() + 1];
    	s = 'x' + s;
    	int max = 0;
    	char[] chars = s.toCharArray();
    	for (int i = 2; i < chars.length; i++) {
    		if (chars[i] == ')') {
    			if (chars[i - 1] == '(') dp[i] = dp[i - 2] + 2;
    			else if (chars[i - dp[i - 1] - 1] == '(') dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2;
    			max = Math.max(max, dp[i]);
    		}
    	}
    	return max;
    }
    

Log in to reply
 

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