[B] [C] [D]

You are given a string s composed of ‘(‘, ‘)’ and lowercase letters.

You need to remove the minimum number of ‘(‘ or ‘)’ (you can remove parentheses anywhere) from the string to make the rest of the ‘parenthesis string’ valid.

Please return any valid string.

A valid “parenthesis string” should meet any of the following requirements:

  • An empty string or a string containing only lowercase characters
  • Can be writtenAB(AThe connectionB), whereA 和 BAll valid parenthesis strings.
  • Can be written(A)The string, whereAIs a valid parenthesis string.

Example 1:

Input: s = "lee (t) (c) o DE)" output: "lee (t) (c) o DE" explanation: "lee (t (co) DE)", "lee (t (c) the ode)" is also a possible answer.Copy the code

Example 2:

Input: s = "a)b(c)d" output: "ab(c)d"Copy the code

Example 3:

Input: s = "))((" output: "" Explanation: Empty strings are also validCopy the code

Example 4:

Input: s = "(a(b(c)d)" output: "a(b(c)d)Copy the code

Tip:

  • 1 <= s.length <= 10^5
  • s[i]May be'(',') 'Or English lowercase letters

Delete invalid parentheses from the input string

When it comes to matching parentheses, you can use the stack to solve the problem

Because the nature of the stack is first in, last out, so when the open parenthesis is maintained by the stack, when the close parenthesis is encountered, if the stack is not empty, the top element of the stack is the open parenthesis corresponding to the current close parenthesis

This case also uses this technique to push the corresponding subscript onto the stack if the current character is an open parenthesis while iterating through the input string

If the current character is a close parenthesis, check whether the stack is empty

If the stack is not empty, the top element of the stack is the open parenthesis corresponding to the current close parenthesis, and the top element of the stack is ejected and traversal continues

If the stack is empty, there is no matching open bracket in the current close bracket, and the close bracket is invalid and removed from the input string

If the current character is lowercase, no operation is required

So when the input string is iterated, all invalid close parentheses are removed, and if the stack is not empty, the stack is saved to the subscript of all invalid open parentheses

Pops the top element of the stack and removes the corresponding character from the input string until the stack is empty

Finally, return the processed input string

The process is shown as follows:

The code is as follows:

Var minRemoveToMakeValid = function(s) {const stack = []; // iterate over the input string for(let I = 0; i<s.length; I++) {/ / if they are left parenthesis, the subscript stack the if (s = = = '(') [I] {stack. Push (I)} else if (s = = = [I]') ') {/ / if it is right parenthesis / / if the stack is empty, that the top left parenthesis for the corresponding right parenthesis left parenthesis, Pop (stack.length) stack.pop(); Else {s = s.substring(0, I)+s.substring(I +1); i--; While (stack.length){const ind = stack.pop(); const ind = stack.pop(); S = s.substring(0,ind)+s.substring(ind+1)} };Copy the code

At this point we are done with Leetcode-1249 – removing invalid parentheses

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