1249 Minimum Remove to Make Valid Parentheses 移除無效的括號
Description:
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:
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.
Constraints:
1 <= s.length <= 10^5
s[i] is either'(' , ')', or lowercase English letter.
題目描述：
給你一個由 '('赁还、')' 和小寫字母組成的字符串 s乔遮。
你需要從字符串中刪除最少數(shù)目的 '(' 或者 ')' （可以刪除任意位置的括號)央串，使得剩下的「括號字符串」有效。
請返回任意一個合法字符串刺啦。
有效「括號字符串」應(yīng)當符合以下 任意一條 要求：
空字符串或只包含小寫字母的字符串
可以被寫作 AB（A 連接 B）的字符串，其中 A 和 B 都是有效「括號字符串」
可以被寫作 (A) 的字符串，其中 A 是一個有效的「括號字符串」
示例：
示例 1：
輸入：s = "lee(t(c)o)de)"
輸出："lee(t(c)o)de"
解釋："lee(t(co)de)" , "lee(t(c)ode)" 也是一個可行答案哮针。
示例 2：
輸入：s = "a)b(c)d"
輸出："ab(c)d"
示例 3：
輸入：s = "))(("
輸出：""
解釋：空字符串也是有效的
提示：
1 <= s.length <= 10^5
s[i] 可能是 '('、')' 或英文小寫字母
思路：
棧
用一個棧 left 記錄出現(xiàn)的左括號的位置
每次遇到右括號, 如果棧非空就彈出
否則加入到哈希表中
最后棧中的元素都加入哈希表中, 哈希表中都是需要刪除的不匹配括號的下標
時間復(fù)雜度為 O(n), 空間復(fù)雜度為 O(n)
代碼:
C++:
class Solution
{
public:
string minRemoveToMakeValid(string s)
{
int n = s.size();
unordered_set<int> right;
stack<int> left;
for (int i = 0; i < n; i++)
{
if (s[i] == '(') left.push(i);
else if (s[i] == ')')
{
if (!left.empty()) left.pop();
else right.insert(i);
}
}
while (!left.empty())
{
right.insert(left.top());
left.pop();
}
string result = "";
for (int i = 0; i < n; i++) if (!right.count(i)) result += s[i];
return result;
}
};
Java:
class Solution {
public String minRemoveToMakeValid(String s) {
int n = s.length();
Set<Integer> right = new HashSet<>();
Stack<Integer> left = new Stack<>();
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '(') left.push(i);
else if (s.charAt(i) == ')') {
if (!left.isEmpty()) left.pop();
else right.add(i);
}
}
while (!left.isEmpty()) right.add(left.pop());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) if (!right.contains(i)) sb.append(s.charAt(i));
return sb.toString();
}
}
Python:
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
right, left = set(), []
for i, c in enumerate(s):
if c == "(":
left.append(i)
elif c == ")":
if left:
left.pop()
else:
right.add(i)
right |= set(left)
return "".join([c for i, c in enumerate(s) if i not in right])
