题目描述
给你一个由 '('
、')'
和小写字母组成的字符串 s
。
你需要从字符串中删除最少数目的 '('
或者 ')'
(可以删除任意位置的括号),使得剩下的括号字符串有效。
请返回任意一个合法字符串。
有效括号字符串应当符合以下要求:
- 空字符串或只包含小写字母的字符串,或
- 可以被写作
AB
(A
连接B
)的字符串,其中A
和B
都是有效括号字符串,或 - 可以被写作
(A)
的字符串,其中A
是一个有效的括号字符串。
样例
输入:s = "lee(t(c)o)de)"
输出:"lee(t(c)o)de"
解释:"lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。
输入:s = "a)b(c)d"
输出:"ab(c)d"
输入:s = "))(("
输出:""
解释:空字符串也是有效的
输入:s = "(a(b(c)d)"
输出:"a(b(c)d)"
限制
1 <= s.length <= 10^5
s[i]
可能是'('
、')'
或英文小写字母。
算法1
(两次线性扫描) $O(n)$
- 两次线性扫描,第一次从左到右扫描。维护一个计数器,遇到左括号,计数器加 1,加入左括号。遇到右括号,如果计数器为 0,则不加入右括号。遇到字母直接加入。
- 第二次在第一次统计出的数组上再进行一次扫描,从右到左扫描。维护一个计数器,遇到右括号,计数器加 1,加入右括号。遇到左括号,如果计数器为 0,则不加入左括号。遇到字母直接加入。
- 两次扫描结束之后的答案就是最终的合法答案。
时间复杂度
- 两次线性扫描,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的空间记录中间和答案字符串。
C++ 代码
class Solution {
public:
string minRemoveToMakeValid(string s) {
int n = s.length();
string t;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '(') {
cnt++;
t += s[i];
} else if (s[i] == ')') {
if (cnt > 0) {
cnt--;
t += s[i];
}
} else {
t += s[i];
}
}
cnt = 0;
string ans;
for (int i = t.length() - 1; i >= 0; i--)
if (t[i] == ')') {
cnt++;
ans += t[i];
} else if (t[i] == '(') {
if (cnt > 0) {
cnt--;
ans += t[i];
}
} else {
ans += t[i];
}
reverse(ans.begin(), ans.end());
return ans;
}
};
算法2
(栈) $O(n)$
- 使用栈来维护括号,同时开一个数组记录哪些位置是不合法的。
- 遇到左括号,则当前位置进栈。遇到右括号,如果栈空,则当前位置不合法,否则栈顶出栈。
- 最后如果栈不空,则栈中所有的位置标记为不合法。
时间复杂度
- 每个位置遍历常数次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的空间存放栈,标记数组和答案字符串。
C++ 代码
class Solution {
public:
string minRemoveToMakeValid(string s) {
int n = s.length();
stack<int> st;
vector<bool> v(n, true);
for (int i = 0; i < n; i++) {
if (s[i] == ')') {
if (st.empty()) v[i] = false;
else st.pop();
} else if (s[i] == '(') {
st.push(i);
}
}
while (!st.empty()) {
v[st.top()] = false;
st.pop();
}
string ans;
for (int i = 0; i < n; i++)
if (v[i])
ans += s[i];
return ans;
}
};