You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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:
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.
Example 2:
Input: s = "a)b(c)d"
Output: "ab(c)d"
Example 3:
Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.
Example 4:
Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"
Constraints:
1 <= s.length <= 10^5
s[i] is one of '(' , ')' and lowercase English letters.
Minimum Remove to Make Valid Parentheses
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:
AB
(A
concatenated withB
), whereA
andB
are valid strings, or(A)
, whereA
is a valid string.Example 1:
Example 2:
Example 3:
Example 4:
Constraints:
1 <= s.length <= 10^5
s[i]
is one of'('
,')'
and lowercase English letters.
算法思路:利用栈来解决这题,栈中存储下标。从左到有遍历字符串,如果先出现
)
,则此位置的)
直接不可用;如果出现(
,则将下标压进栈中,继续遍历;再遇到)
,则查看栈中是否有(
,如果有则将其弹出,否则,此位置的)
不可用。The text was updated successfully, but these errors were encountered: