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:
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.
A:
就是每次找配对儿的。找不到,则标记为不行
class Solution { public: string minRemoveToMakeValid(string s) { int n = s.length(); vector<bool> deleted(n,false); stack<int> S;// stack of (, waiting to be matched. for(int i =0;i<n;i++){ char ch = s[i]; if(ch == '('){ S.push(i); }else if(ch ==')'){ if(S.empty()){ deleted[i] = true; }else{ S.pop(); } } } while(not S.empty()){ int tmp = S.top(); S.pop(); deleted[tmp] = true; } string res = ""; for(int i =0;i<n;i++){ char ch = s[i]; if(not deleted[i]){ res += ch; } } return res; } };
No comments:
Post a Comment