Minimum Remove to Make Valid Parentheses
|Last edited: 2024-5-10
ID
1249
Data Type
Stack
Difficulty
Medium
Tags
URL
https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/
Completed Date
May 10, 2024
Preference
😰 Didn't Expect
Given a string s of '(' , ')' and lowercase English characters.
Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:
  • It is the empty string, contains only lowercase characters, or
  • It can be written as AB (A concatenated with B), where A and B are valid strings, or
  • It can be written as (A), where A is a valid string.
Example 1:
Example 2:
Example 3:
Constraints:
  • 1 <= s.length <= 105
  • s[i] is either '(' , ')', or lowercase English letter.

题解

  1. 要记录栈变空的位置，之前的就不用动了，之后的所有的)全部不要
  1. 这个题不用栈也可以，记录(的出现次数，出现)就-1，在没出现( 之前的) 统统不要，我之前还在想怎么记录每次闭合的位置，以防出现())()这种情况，但是实际上可以直接边写边处理，多余的(都在右边，所以可以倒找处理，还是没想到
 
这样处理就太复杂了，还处理不好