[Luffy]_ Remove invalid brackets tonight

Remove invalid parentheses

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”

The sample

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

That’s what I was thinking when I was doing the problem

Ignore letters:

Suppose the string has: s = “(())(()”

To observe the

You can obviously see that there is an extra “(” close parenthesis;

The first time I enumerate the invalid parenthesis subscript, and the second time I enumerate the invalid parenthesis subscript, ignore the invalid parenthesis subscript and get the answer.

How do I record this position?

When the first thought of valid parentheses occurs in pairs, only the right parentheses touch the left parentheses to form valid parentheses; Here comes the idea;

Save invalid open parenthesis subscripts with array list, and invalid close parenthesis subscripts with array rightList; The saving rules are as follows:

• When the left parenthesis [“(“]; Put the subscript in an array, because if there is no close parenthesis, the current parenthesis is invalid;
• When close parenthesis is encountered, classification is discussed:
  • If the list array is empty, no (; Place the current coordinates on rightList
  • If the list array is not empty, the last bit of the list is removed, because the current close parentheses form valid parentheses with the open parentheses in the list array
• Enumeration complete, resulting in list and rightList are invalid parenthesis subscripts;
• Enumerating once, ignoring the subscript strings in the list and rightList arrays; You get the answer

code

var minRemoveToMakeValid = function(s) {
    let len = s.length;
    let list = [];
    let leftlist = [];
    let str = ' '
    for(let i = 0 ; i < len ; i++){
        if(s[i] === '('){
          list.push(i)
        }else if(s[i] === ') ') {if(list.length === 0){
               leftlist.push(i)
           }else{ list.pop(); }}}const limit = leftlist.concat(list)
    for(let i = 0 ; i < len ; i++){
        if(! limit.includes(i))str+=s[i] }return str

};
Copy the code

The optimized

It can also be AC, but it uses extra space and two arrays. Optimize it;

How do you optimize?

Considering the optimization point, there is no way to optimize enumeration, just to see if the array can not be used.

Can we invalidate parenthesis data without array records?

Observe s = “(())(()”

The first time through the enumeration you can actually remove the (left parenthesis;

Observe s = “))))(()”

The first enumeration removes all invalid (open parentheses, but does not determine invalid close parentheses

That’s where the idea comes in.

The first enumeration removes invalid open parentheses from left to right,

The second enumeration removes the invalid close parentheses from right to left.

For example

Suppose s = “))))(()” num = 0; Num is used to record the number of open parentheses,

• A close parenthesis is encountered when num is 0, and is ignored
• When num is greater than 0; When a close parenthesis is encountered, save the close parenthesis to a new string, num-1;

The new string is returned after the enumeration

Look at the new string, num=1;

The new string has exactly one more open parenthesis;

New string enumerates from right to left, num left parentheses encountered, ignored;

Then we get:

Ha ha, done

code

var minRemoveToMakeValid = function(s) {
    let len = s.length;
    let str = ' '
    let num = 0;
    for(let i = 0 ; i < len ; i++){
        if(s[i] === '('){
          num++;
          str+=s[i]
        }else if(s[i] === ') ') {if(num === 0){
           }else{ str+=s[i]; num--; }}else{ str+=s[i]; }}if(num === 0) return str;
    let result = ' '
    for(let i =  str.length-1; i>=0 ; i--){
        if(str[i] === '(' && num > 0){
            num--;
            continue
        }
        result =   str[i] + result 
    }
    return result

};
Copy the code