[B] [C] [D]

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

  • For example,""."()"."() () ()" 和 "() () () ()"Both 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 primitive, where A and B are non-empty valid parenthesis strings.

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

The primitive decomposition of S is performed, removing the outermost parentheses of each primitive string in the decomposition and returning S.

Example 1:

Input: s = "(()())(())" output: "()()() ()()()" Input string for "() () () () ()", the original forms of the decomposed "() () ()" + "() ()", delete the outermost parentheses after each part of "() ()" + "()" = "() () ()".Copy the code

Example 2:

Input: s = "() () () () () () () () ()" output: "() () () () () ()" explanation: Input string for "() () () () () () () () ()", the original forms of the decomposed "() () ()" + "() ()" + "() () () ()", Delete each part of the parentheses after the outermost layers of the "() ()" + "()" + "() () ()" = "() () () () () ()".Copy the code

Example 3:

Input: s = "() ()" output: "" explanation: the input string as the" () () ", the primitive is decomposed "()" + "()", delete the parentheses after the outermost layers of each part "" +" "=" ".Copy the code

Tip:

  • 1 <= s.length <= 105
  • s[i] 为 '(' 或 ') '
  • sIs a valid parenthesis string

So if you want to remove all the parentheses from the input string, the easiest way to remove all the parentheses is to split the input string by parentheses and put it into an array

Then loop through the array, removing the outermost parentheses from each substring, and concatenating the remaining substrings to form the resulting string

But this operation requires two cycles and is not the optimal solution in this case

We can unpack the desired result string in a single loop of input

The solution is as follows:

  1. Initialize thel = 0Record the number of open parentheses,r = 0Record the number of closing parentheses,left = 0Record the beginning subscript of this interval,res = ""Record result string
  2. Iterate over the string and update the related variables. When the current character is(The time,l++And vice versar++
  3. whenl === rA set of outermost parentheses has been foundleftSubscript refers to the left parenthesis subscript, currently traversing the subscriptiPoints to the close parenthesis subscript, intercepting the middle part of the two subscripts, which is part of the result string we want
  4. resetl = 0.r = 0.left = i+1, repeat the above process until the input string traversal is complete
  5. At this timeresThe resulting string is stored in

The overall process is as follows:

The code is as follows:

Var removeOuterParentheses = function(s) {" count ", "count", "count", "count".  // iterate over the input string for(let I = 0; i<s.length; If (s[I]==='(') l++; else r++; If (l===r){if(l===r){res += s.substring(left+1, I); // Set the number of parentheses to 0. r = 0; // Update the starting subscript to the next outermost parenthesis left = I +1; }} // Return the result string return res; };Copy the code

At this point we are done with Leetcode-1021 – removing the outermost parentheses

If you have any questions or suggestions, please leave a comment!