This is the NTH day of my participation in the August More Text Challenge. For details, see:August is more challenging

preface

I wanted to participate in the Action in June, but I couldn’t because of my own reasons. I’d like to come this time in August. I hope that through this activity, I can gradually develop a good habit of output. And constantly improve their own level, output good articles. Also hope to make more friends. Grow together.

I hope you can see the shortcomings and comment more! Thank you very much!

The title

Valid parenthesis strings are empty “”, “(” + A + “)”, or A + B, where A and B are valid parenthesis strings, and + represents concatenation of strings.

For example, “”, “()”, “()”, “(())()” and “(()(()))” are valid parenthesis strings. If the valid string S is non-empty and there is no way to split it into s = A + B, we call it A primitive, where both A and B are non-empty valid parenthetical strings.

Given a non-null valid string S, consider primitive decomposition such that s = P_1 + P_2 +… + P_k, where P_i is a valid parenthesis string primitive.

Primitive decomposition of S, removing the outermost parentheses of each primitive string in the decomposition, returns S.

Source: LeetCode link: leetcode-cn.com/problems/re…

The test case

Example 1:

Enter: s ="() () () () ()"Output:"() () ()"
Copy the code

Example 2:

Enter: s ="() () () () () () () () ()"Output:"() () () () () ()"
Copy the code

Method 1: Profiteering crack (decompose, recycle in merge)

Implementation process:

  1. Validate primitives: By counting the number of left and right parentheses, if the number is the same, the string in parentheses is a primitive
  2. Store the primitives in the new array
  3. Loop through the primitive, removing the outermost parentheses, and append to the string

Specific methods:

  • Create a new ArrayList<>() to store the primitives
  • Definition:
    • Left = 0 Number of open parentheses
    • Right = 0 number of close parentheses
    • LastOpr = 0 The last digit of the primitive string
  • Loop through the characters
    • Character == ‘(‘ : left++
    • Character == ‘) ‘: right++
    • When left == right indicates a primitive, intercept the string and store it in an array of primitives
  • Iterate over the array of primitives
    • Intercepts and appends to a string

code

public String test1(String s) {
    // Profiteering
    int len = s.length();
    List<String> strings = new ArrayList<String>();

    int left = 0, right = 0, lastOpr = 0;
    for (int i = 0; i < len; i++) {
        char c = s.charAt(i);
        if (c == '(') {
            left++;
        } else if (c == ') ') {
            right++;
        }
        if (left == right) {
            strings.add(s.substring(lastOpr, i + 1));
            lastOpr = i + 1;
        }
    }

    StringBuilder stringBuilder = new StringBuilder();
    for (String string : strings) {
        stringBuilder.append(string.substring(1, string.length() - 1));
    }
    return stringBuilder.toString();
}
Copy the code

Method 2: windfall cracking (after positioning, directly merge)

Optimization: Remove the array of primitives. After obtaining the string of primitives, delete the outermost brackets of primitives directly and store them in the array


public String test2(String s) {
    int len = s.length();
    StringBuilder stringBuilder = new StringBuilder();
    int left = 0, right = 0, lastOpr = 0;
    for (int i = 0; i < len; i++) {
        char c = s.charAt(i);
        if (c == '(') {
            left++;
        } else if (c == ') ') {
            right++;
        }
        if (left == right) {
            stringBuilder.append(s.substring(++lastOpr, i));
            lastOpr = i + 1; }}return stringBuilder.toString();
}
Copy the code

Method three: use the counter mode

The number of parentheses is calculated by the integer field (count). An open parenthesis + 1 and a close parenthesis -1 appear

Implementation process:

  • Emphasis:
  • When the character is equal to the open parenthesis:
    • We first determine that count > 0, that is, the character is a valid character within the primitive, and store the character in the new string
    • So we’re going to add count++
  • When the character is equal to the closing parenthesis:
    • Let’s do the calculation first and decrementing the value count —
    • After determining that count > 0, that is, the character is a valid character within the primitive, the character is stored in the new string
public String arrayNumsTest(String s) {
    StringBuilder stringBuilder = new StringBuilder();
    int count = 0;
    int len = s.length();
    char[] chars = s.toCharArray();
    for (int i =0 ; i<len; i++) {
        char c = chars[i];
        if (c == '(') {
            if (count > 0) {
                stringBuilder.append(c);
            }
            count++;
        } else {
            count--;
            if (count > 0) { stringBuilder.append(c); }}}return stringBuilder.toString();

}
Copy the code