Delete the outermost parentheses

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, “”, “()”, “()”, “(())()” 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 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: "()()()()()()()()()()()())" 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

Traversal + parentheses open state record string

Train of thought

There must be a state in which parentheses are open and closed

We use score to represent the parentheses to represent the status,

  • When (score+=1, score+=1, otherwise) the proof parenthesis is closed, score-=1, so that when score>0 the parenthesis is open, otherwise the parenthesis is closed
  • We need to record the string we encounter after the parentheses are opened, and we need to skip it when the parentheses are closed

Note: the two strings when parentheses are opened and closed do not need to be recorded.

  • When we encounter (parentheses, we judge whether score is greater than 1. If yes, it represents the internal parentheses after the parentheses are opened. If ===1, we prove that this time is the parentheses are opened without record
  • Check if score is 0 when parentheses are encountered. If so, the parentheses are closed and no record is needed
var removeOuterParentheses = function (s) {
    var score = 0
    var newStr = ' '
    var i = 0
    while (i < s.length) {
        var item = s[i]
        i++
        if(item==='('){
            score+=1
            if(score>1){
               newStr+=item 
            }
        }else{
            score-=1
            if(score===0) {continue
            }
            newStr+=item 
        }
    }
    return newStr
};
Copy the code