LeetCode brush, remove invalid parentheses (1249)

Remove invalid parentheses

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

You need to remove the minimum number of ‘(‘ or ‘)’ (you can remove any parentheses) from the string in order for the remaining parentheses string to be valid.

The problem solving code

We only need to determine whether the number difference in parentheses is 0. If the number of open parentheses to close parentheses is 0, then all parentheses are matched. If not, just delete the parentheses

var minRemoveToMakeValid = function(s) {
  let res = "";
  let cnt = 0; // Record the difference
  let index = []; // Record the subscript where the open bracket appears
  let continueNum = 0; // Record the number of times the close bracket appears and the difference is less than or equal to 0
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    if (char === "(") {
      cnt += 1; // Open parenthesis + 1 is encountered
      res += char;
      index.push(i); // Record the position of all open parentheses
    } else if (char === ")") {
      if ( cnt <= 0 ) { 
        continueNum += 1; // When the difference is less than or equal to 0, the occurrence of a close parenthesis means that there is an extra close parenthesis, record the number of jump out
        continue
      };
      cnt -= 1; // A close parenthesis of -1 is encountered, indicating that the match has been completed once
      index.shift(); // Delete the matching open parenthesis position
      res += char;
    } else {
      res += char;
    }
  }
  res = res.split("");
  index.forEach(i= > {
    res[i - continueNum] = ""; ContinueNum is subtracting continueNum because when the closing parenthesis is present, the value of the string will be reduced. ContinueNum is subtracting continueNum because when the closing parenthesis is present, the value of the string will be reduced.
  })
  return res.join(""); // Return the final result string
};
Copy the code