“This is the 8th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

Today’s removal of the outermost parentheses was a real code saving, because today we only have to deal with one type of parentheses compared to valid parenthesis strings, and instead of having to do the stack yourself, you can see that the idea really matters.

Topic describes

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.

Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

Train of thought is a little wordy, can jump directly to see the solution, train of thought if you can understand, I really have to thank you

  1. First of all we needIdentify the objective of the problemDon’t get confused by the definition, don’t worry about the primitives, what do we do firstIsolate the valid questions:

    1) They’re asking us to deal with aA valid parenthesis string connector consisting of a valid parenthesis string containing only the parenthesesThe primitives in the question are each subset of valid parenthesis strings

    2) What we’re going to do isRemove the outermost parenthesis from each subset of the valid parenthesis string
  2. So the first step is to find each subset of the valid bracket strings, and the second step is to remove the outermost bracket from the subset of the valid bracket strings, and then concatenate,You think I'm gonna do it in three steps like this?
  3. At first you might think of the valid parenthesis string problem, and you might say, well, why don’t I just go through and look for valid parenthesis strings, and when I find one, I remove the parenthesis, I save it, and then I concatenate it, but can I concatenate it while I’m going through? And it’s okIs the result achieved in one step by filtering out the outermost parentheses of the valid parentheses subset of the string that we want to delete during traversal?
  4. So how do you do it?

    When I parse the string of valid parentheses, I always think that there are some closed ideas in it, but there are three kinds of parentheses, but today there are only one kind of parentheses, just +1, -1 summation is not enough.

    1) The open parenthesis represents +1 and the close parenthesis represents -1. If you want to form valid parentheses, do you have to sum sum 0, butOur goal is not to sum, but to filter and concatenate the final resultSum = 1 means we’ve dealt with at least one open parenthesis

    2) So, when do we concatenate the open parenthesis?We concatenate when sum represents the number of open parentheses (sum>0).I’m just going to remove the first open parenthesis

    3) When do we concatenate if we have a close parenthesis, first we have to subtract 1 from sum,When sum represents at least 2 of the open parentheses that we've been working with in order to concatenate this close parenthesis, that's the case, sum>1

    4) At the end of the first valid parenthesis string,sum =0, the digit before sum is 1, and the digit before sum is 2, which is the digit of the concatenation

To the problem solving

Although nonsense along the way, but I do the summary of the idea, hard along the way, a few lines of code, ha ha

var removeOuterParentheses = function(s) { let res = ''; let sum = 0; For (char of s) {for(char of s) {sum>0 indicates that there is at least one open parenthesis whose 0 has not been eliminated, so we can continue to concatenate the open parenthesis. There must be at least two uneliminated open parentheses: sum>1 // sum++ and sum. If encounter right parenthesis sum - 1 (char = = = '(' && sum++ > 0) | | (char = = =') '&& sum - > 1)) res + = char; } return res; };Copy the code