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, if`dp[i-1]`Is preceded by a close parenthesis, then`dp[i]` = 0
• The I position is the close bracket, if`dp[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``````