0301. Remove Invalid Parentheses¶
题目信息¶
- 题号:
0301
- 难度:
Hard
- 主题:
字符串、括号合法性、结果去重、最少删除
- 原题:
- 重点:
只能删除圆括号、删除数量必须最少、普通字母保留原顺序、返回全部不同的最优结果
题目重述¶
给定字符串 s,其中只包含小写英文字母、左括号 ( 和右括号 )。可以从任意位置删除圆括号,字母不能删除。需要删除尽可能少的括号,使剩余字符串中的所有括号正确配对。
返回经过最少删除后能够得到的所有不同合法字符串,结果顺序不限。s 的长度位于 [1, 25],其中圆括号总数不超过 20。合法字符串允许没有任何括号;不同删除位置若产生相同字符串,结果中只能保留一次。
自建示例¶
同时存在多余右括号和左括号:
输入:s = "a())("
输出:["a()"]
解释:必须删除一个多余的右括号和末尾无法配对的左括号,最少删除数为 2;删除两个相邻右括号中的任意一个都会得到同一个结果,因此只返回一次。
不同删除方式产生不同最优结果:
输入:s = "r(s)())"
输出:["r(s())", "r(s)()"]
解释:只需删除一个右括号即可合法;删除 ``s`` 后面的第一个右括号得到 ``r(s())``,删除末尾一组中的一个右括号得到 ``r(s)()``,二者都应返回,顺序不限。
先确定必须删除多少¶
不能在搜索过程中只要得到一个合法字符串就停止,因为题目要求返回所有“删除数最少”的结果。先从左到右扫描括号:遇到 ( 就增加当前未配对的左括号数;遇到 ) 时,若有未配对的 ( 就配掉一个,否则这个右括号必然需要删除。扫描结束后,剩下的未配对左括号数就是必须删除的左括号数,扫描途中积累的多余右括号数就是必须删除的右括号数。
这两个数量给出了全局最少删除数。原因是多余的右括号无法通过删除别处修复,多余的左括号也不可能在后面凭空找到右括号;而删除这些括号后,原字符串中其余括号可以保持配对关系。因此后续搜索只枚举恰好删除这两类数量的方案。
按删除预算回溯¶
回溯从左到右处理每个字符,状态包含当前位置、剩余的左右括号删除预算、当前括号余额以及已经保留的字符串。字母只能保留;左括号可以在有删除预算时删除,也可以保留并使余额加一;右括号可以在有删除预算时删除,也只有余额大于零时才能保留并使余额减一。余额变成负数时,当前分支已经不可能合法,立即剪枝。
到达字符串末尾时,只有删除预算全部用完且余额为零的路径才是答案。不同删除位置可能生成同一个字符串,使用集合去重;这不会改变“只枚举最少删除数”的性质。由于圆括号总数最多 20,按删除预算搜索的规模可接受。
C++ 实现¶
class Solution {
void dfs(const std::string& s, int pos, int leftRemove,
int rightRemove, int balance, std::string& path,
std::set<std::string>& answers) {
if (balance < 0 || leftRemove < 0 || rightRemove < 0) {
return;
}
if (pos == static_cast<int>(s.size())) {
if (leftRemove == 0 && rightRemove == 0 && balance == 0) {
answers.insert(path);
}
return;
}
char current = s[pos];
if (current == '(') {
if (leftRemove > 0) {
dfs(s, pos + 1, leftRemove - 1, rightRemove,
balance, path, answers);
}
path.push_back(current);
dfs(s, pos + 1, leftRemove, rightRemove,
balance + 1, path, answers);
path.pop_back();
} else if (current == ')') {
if (rightRemove > 0) {
dfs(s, pos + 1, leftRemove, rightRemove - 1,
balance, path, answers);
}
if (balance > 0) {
path.push_back(current);
dfs(s, pos + 1, leftRemove, rightRemove,
balance - 1, path, answers);
path.pop_back();
}
} else {
path.push_back(current);
dfs(s, pos + 1, leftRemove, rightRemove,
balance, path, answers);
path.pop_back();
}
}
public:
std::vector<std::string> removeInvalidParentheses(std::string s) {
int leftRemove = 0;
int rightRemove = 0;
for (char current : s) {
if (current == '(') {
++leftRemove;
} else if (current == ')') {
if (leftRemove > 0) {
--leftRemove;
} else {
++rightRemove;
}
}
}
std::set<std::string> answers;
std::string path;
dfs(s, 0, leftRemove, rightRemove, 0, path, answers);
return std::vector<std::string>(answers.begin(), answers.end());
}
};
代码分析¶
初次扫描把不可避免的删除量固定下来,回溯不会产生删除更多括号的“次优”结果;余额状态则保证保留下来的右括号始终有对应的左括号。字母分支只有保留这一种选择,所以字母顺序不会改变。设括号数为 p、字符串长度为 n,删除方案最多按 O(2^p) 级别枚举,构造和放入结果集合还要付出字符串及集合操作的开销;额外搜索空间为 O(n),不计输出集合本身。