Make writing a habit together! This is the sixth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

In the parenthesis questions series, you will learn how to define the meaning of dynamic programming through finite variable solutions.

I. Parenthesis problem I

Parenthesis valid pairing means:

1) Any open parenthesis will find a correct matching close parenthesis

2) Any close parenthesis will find a matching open parenthesis

()() ()() ()() ()() ()(

Invalid: (), (), (), (

How do I determine if a parenthesis string is valid?

1, analysis,

If count is less than 0, there are more close parentheses than open parentheses, so I don’t need to look at that, so I’m just going to return false, if I’m done iterating, count == 0, it’s valid, otherwise it’s invalid

2, implementation,

public static boolean valid(String s) {
    if (s == null || s.length() == 0) {
        return false;
    }
    char[] str = s.toCharArray();
    int count = 0;
    for (int i = 0; i < str.length; i++) {
        count += str[i] == '(' ? 1 : -1;
        if (count < 0) {
            return false; }}return count == 0;
}
Copy the code

II. Parenthesis problem II

Parenthesis valid pairing means:

1) Any open parenthesis will find a correct matching close parenthesis

2) Any close parenthesis will find a matching open parenthesis

()() ()() ()() ()() ()(

Invalid: (), (), (), (

If a parenthesis string is invalid, return at least a few characters to make it valid as a whole

1, analysis,

Need, if count == -1, there is one more open parenthesis than open parenthesis, need++, count goes back to 0, count = 0, if count > 0, the open parenthesis is bigger than the close parenthesis, The close parentheses need to be compensated for count times, so at least need + count needs to be added, or at least need if count == 0

2, implementation,

public static int needParentheses(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    char[] str = s.toCharArray();
    int count = 0;
    int need = 0;
    for (int i = 0; i < str.length; i++) {
        if (str[i] == '(') {
            count++;
        } else { // 遇到的是')'
            if (count == 0) {
                need++;
            } else{ count--; }}}return count + need;
}
Copy the code

3. Parenthesis problem III

Parenthesis valid pairing means:

1) Any open parenthesis will find a correct matching close parenthesis

2) Any close parenthesis will find a matching open parenthesis

Returns the maximum number of nesting layers in a valid parenthesis string

For example :(()()) returns 2 levels, (()(())) returns 3 levels, and ()(()) returns 2 levels

1, analysis,

I’m going to have an open parenthesis count++, I’m going to have a close parenthesis count– the maximum value of count is how many layers are nested

2, implementation,

// Check whether the parentheses are valid
public static boolean isValid(char[] str) {
    if (str == null || str.length == 0) {
        return false;
    }
    int status = 0;
    for (int i = 0; i < str.length; i++) {
        if(str[i] ! =') '&& str[i] ! ='(') {
            return false;
        }
        if (str[i] == ') ' && --status < 0) {
            return false;
        }
        if (str[i] == '(') { status++; }}return status == 0;
}

public static int deep(String s) {
    char[] str = s.toCharArray();
    if(! isValid(str)) {return 0;
    }
    int count = 0;
    int max = 0;
    for (int i = 0; i < str.length; i++) {
        if (str[i] == '(') {
            max = Math.max(max, ++count);
        } else{ count--; }}return max;
}
Copy the code

Question IV

Parenthesis valid pairing means:

1) Any open parenthesis will find a correct matching close parenthesis

2) Any close parenthesis will find a matching open parenthesis

Returns the length of the longest parenthesis valid substring in a parenthesis string

1, analysis,

The substring must be continuous

End with what

If I encounters an open parenthesis, then dp[I] is equal to 0, because it is impossible for a valid parenthesis to end in an open parenthesis, violating the meaning of the dp[I] definition

Dp [I] = 5 if the parenthesis is open at i-5, dp[I] = 0 if the parenthesis is close at i-5, dp[I] = 4 if the parenthesis is open at i-5, dp[I] = 0 if the parenthesis is close at i-5, dp[I] = 4 if the parenthesis is open at i-5, dp[I] = 0 It is also 0 because dp[I] is the longest valid parenthesis substring that can be matched. Dp [i-1] already records the length of the longest valid parenthesis substring, even if the left parenthesis matches, it is the calculated value of dp[i-1]

  • The I position is the close bracket, ifdp[i-1]Is preceded by a close parenthesis, thendp[i] = 0
  • The I position is the close bracket, ifdp[i-1]If the first digit of is an open parenthesis, then dp[I] is at least dp[i-1] + 2

2, implementation,

public static int maxLength(String s) {
    if (s == null || s.length() < 2) {
        return 0;
    }
    char[] str = s.toCharArray();
    int[] dp = new int[str.length];
    int pre = 0;
    int ans = 0;
    // dp[0] = 0;
    for (int i = 1; i < str.length; i++) {
        if (str[i] == ') ') {
            pre = i - dp[i - 1] - 1; // Position of the left parenthesis paired with STR [I] pre
            if (pre >= 0 && str[pre] == '(') {
                dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
            }
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}
Copy the code