Minimum Remove to Make Valid Parentheses
ID
1249
Data Type
Stack
Difficulty
Medium
Tags
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 withB
), whereA
andB
are valid strings, or
- It can be written as
(A)
, whereA
is a valid string.
Example 1:
Example 2:
Example 3:
Constraints:
1 <= s.length <= 105
s[i]
is either'('
,')'
, or lowercase English letter.
题解
- 要记录栈变空的位置,之前的就不用动了,之后的所有的
)
全部不要
- 这个题不用栈也可以,记录
(
的出现次数,出现)
就-1,在没出现(
之前的)
统统不要,我之前还在想怎么记录每次闭合的位置,以防出现())()
这种情况,但是实际上可以直接边写边处理,多余的(
都在右边,所以可以倒找处理,还是没想到
这样处理就太复杂了,还处理不好