题目描述
给你一个由若干括号和字母组成的字符串 s
,删除最小数量的无效括号,使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
样例
输入:s = "()())()"
输出:["(())()","()()()"]
输入:s = "(a)())()"
输出:["(a())()","(a)()()"]
输入:s = ")("
输出:[""]
限制
1 <= s.length <= 25
s
由小写英文字母以及括号'('
和')'
组成。s
中至多含20
个括号。
算法
(递归回溯枚举) $O(n \cdot 2^n)$
- 先线性扫描一遍,求出需要删除的左括号和右括号的个数。
- 然后递归枚举,递归时,追踪当前未匹配左括号的数目,如果左括号数目为 0,则不能保留当前的右括号。
- 这里介绍一个优化,我们可以直接在枚举的过程中去重:对于一段连续的
'('
或者')'
,我们枚举需要从这段连续的括号中删除的数量,然后递归,这样可以避免生存重复的答案。 - 基于这个优化,这里需要多一个预处理,即将字符串转换为一个数组,数组的元素是一个数对,数对的第一位为字符,第二位为该字符的数量。这个优化可以很快地处理
((((....(((()
的数据。
时间复杂度
- 最坏情况下每个位置有两种选择,去掉和不去掉,最后需要 $O(n)$ 的时间拷贝答案,故时间复杂度为 $O(n\cdot 2^n)$。
空间复杂度
- 预处理需要 $O(n)$ 的空间,递归需要 $O(n)$ 的空间,记录答案需要和答案相同数量的空间。
C++ 代码
class Solution {
public:
void solve(int cur, int n, const vector<pair<char, int>>& st,
int left, int left_rm, int right_rm,
string& tmp_str, vector<string>& ans) {
if (cur == n) {
if (left == 0)
ans.push_back(tmp_str);
return;
}
auto &c = st[cur];
if (c.first == '(') {
tmp_str += string(c.second, '(');
for (int i = 0; i <= c.second; i++) {
if (left_rm >= i)
solve(cur + 1, n, st, left + c.second - i,
left_rm - i, right_rm, tmp_str, ans);
if (i < c.second)
tmp_str.pop_back();
}
} else if (c.first == ')') {
tmp_str += string(c.second, ')');
for (int i = 0; i <= c.second; i++) {
if (right_rm >= i && left >= c.second - i)
solve(cur + 1, n, st, left - c.second + i,
left_rm, right_rm - i, tmp_str, ans);
if (i < c.second)
tmp_str.pop_back();
}
} else {
tmp_str.push_back(c.first);
solve(cur + 1, n, st, left, left_rm, right_rm, tmp_str, ans);
tmp_str.pop_back();
}
}
vector<string> removeInvalidParentheses(string s) {
int n = s.length();
int left_rm = 0, right_rm = 0;
for (int i = 0; i < n; i++)
if (s[i] == '(')
left_rm++;
else if (s[i] == ')') {
if (left_rm == 0)
right_rm++;
else {
left_rm--;
}
}
vector<pair<char, int>> st;
int last = 0;
for (int i = 1; i < n; i++)
if (s[i] != s[i - 1]) {
st.emplace_back(s[i - 1], i - last);
last = i;
}
st.emplace_back(s[n - 1], n - last);
n = st.size();
string tmp_str;
vector<string> ans;
solve(0, n, st, 0, left_rm, right_rm, tmp_str, ans);
return ans;
}
};
Follow up
如果此题只需要求出方案数,则我们可以考虑用动态规划。
- $f(i, j, k)$ 表示考虑了前 $i$ 个字符,此时剩余 $j$ 个字符未匹配,已经删除了 $k$ 个字符的方案数。
- 转移和递归枚举时的想法类似,但要保证每连续的一段括号整体考虑。
时间复杂度
- 状态数为 $O(n^3)$,转移可能需要 $O(n)$ 的时间,理论时间复杂度为 $O(n^4)$,但常数很低。
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
int f[110][110][110];
int main() {
string s;
cin >> s;
int n = s.length();
int m = 0, left = 0;
for (int i = 0; i < n; i++)
if (s[i] == '(')
left++;
else if (s[i] == ')') {
if (left == 0)
m++;
else {
left--;
}
}
m += left;
vector<pair<char, int>> a;
int last = 0;
for (int i = 1; i < n; i++)
if (s[i] != s[i - 1]) {
a.emplace_back(s[i - 1], i - last);
last = i;
}
a.emplace_back(s[n - 1], n - last);
f[0][0][0] = 1;
n = a.size();
int tot = 0;
for (int i = 1; i <= n; i++) {
auto& c = a[i - 1];
tot += c.second;
for (int j = 0; j <= tot; j++)
for (int k = 0; k <= m; k++) {
if (c.first == '(') {
for (int l = 0; l <= c.second; l++)
if (j >= c.second - l && k >= l)
f[i][j][k] += f[i - 1][j - c.second + l][k - l];
} else if (c.first == ')') {
for (int l = 0; l <= c.second; l++)
if (j + c.second - l <= n && k >= l)
f[i][j][k] += f[i - 1][j + c.second - l][k - l];
} else {
f[i][j][k] += f[i - 1][j][k];
}
}
}
cout << f[n][0][m] << endl;
return 0;
}
666
tql ,orz 送给你
大佬太强了