“This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

Remove invalid parentheses from JavaScript version

The title

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:

Empty strings or strings containing only lowercase letters can be written as strings AB (A concatenates B), where both A and B are valid “parenthesis strings” can be written as strings (A), where A is 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.

Example 2:

Input: s = “a)b(c)d” output: “ab(c)d”

Example 3:

Input: s = “))((” output: “” Explanation: Empty strings are also valid

Example 4:

Input: s = “(a(b(c)d)” output: “a(b(c)d)

 

Tip:

1 <= s.length <= 10^5 s[I] may be ‘(‘, ‘)’ or lowercase letters

Answer key

Ask questions

  • There will be letters how should I remove parentheses?

Analysis of the

  • You can see from the problem, the stringsValue contains'(',') 'With the letter
  • Since parentheses are closed in the same order as stack data structures, stack data structures are used to solve the problem, definedleftDel.rightDelStores the current open parenthesis separately'('The right parenthesis') '
  • throughforTraversal strings
  • When an open parenthesis is encountered, passespushInto the stackleftDel
  • When and to close parenthesis, if the current exists'('Delete from the delete list, passpopOut of the stackleftDel
  • Otherwise,') 'Is redundant,pushInto the stackrightDel
  • And then finally you just followleftDel.rightDelThere are subscript delete characters in
  • Hypothesis stringsfor(a(b(c)d)

  • Start iterating through the stringsIn this case, the first digit is an open parenthesis(Therefore, throughpushInto the stackleftDel

  • Repeat the above when an open parenthesis is encountered(Therefore, throughpushInto the stackleftDel

  • Repeat the above when an open parenthesis is encountered(Therefore, throughpushInto the stackleftDel

  • When an open parenthesis is encountered)To determineleftDelIs it empty? If it’s emptypushInto the stackrightDel, otherwise,popOut of the stackleftDel

  • Repeat the above when an open parenthesis is encountered)To determineleftDelIs it empty? If it’s emptypushInto the stackrightDel, otherwise,popOut of the stackleftDel

After iterating through string s, delete the subscript elements in leftDel and rightDel and return the processed string

Code implementation

/** * @param {string} s * @return {string} */ var minRemoveToMakeValid = function(s) { let n = s.length let leftDel = []  let rightDel = [] for(let i = 0; i < n; i++){ const char = s[i] if(char === "("){ leftDel.push(i) }else if(char === ")"){ if(leftDel.length > 0){ leftDel.pop() }else{rightdel.push (I)}} // Delete invalid parentheses according to record let res = [...s] let filter = leftdel.concat (rightDel) let l = filter.length for(let i = 0; i < l; i++){ res[filter[i]] = "" } return res.join("") };Copy the code