题目描述:
给你一个由若干括号和字母组成的字符串 s
,删除最小数量的无效括号,使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
方法一:
class Solution {
public:
vector<string> ans;
unordered_map<string, int> maps;
void dfs(string s, int n, string state,int leftnum, int rightnum, int del_leftnum, int del_rightnum, int index)
{
//前者表示一旦出现右括号数量大于左括号数量,那么一定是错误的
//后者是重要的剪枝,如果要删除的括号数量大于还剩的字符数量,那么可以直接返回
if (rightnum > leftnum || (del_leftnum + del_rightnum > n - index))
{
return;
}
if (index == n) //如果已经读完s了
{
//只要删除了正确数量的左括号和右括号,就是一个有效的字符串,并判断是否有重复字符串
if (del_leftnum == 0 && del_rightnum == 0 && maps.count(state) == 0)
{
ans.push_back(state);
maps[state]++;
}
return;
}
switch (s[index])
{
case '(':
if (del_leftnum > 0)
{
//删除这个左括号
del_leftnum--;
dfs(s, n, state, leftnum, rightnum, del_leftnum, del_rightnum, index + 1);
del_leftnum++;
}
leftnum++;
break;
case ')':
if (del_rightnum > 0)
{
//删除这个右括号
del_rightnum--;
dfs(s, n, state, leftnum, rightnum, del_leftnum, del_rightnum, index + 1);
del_rightnum++;
}
rightnum++;
break;
default:
break;
}
//不管s[index]是什么,不删除s[index]这个字符
state.push_back(s[index]);
dfs(s, n, state, leftnum, rightnum, del_leftnum, del_rightnum, index + 1);
state.pop_back();
}
vector<string> removeInvalidParentheses(string s) {
stack<int> leftsta; //存储左括号
int leftnum = 0; //左括号的数量
int rightnum = 0; //右括号的数量
int del_leftnum = 0; //应该删除的左括号数量
int del_rightnum = 0; //应该删除的右括号的数量
string state;
int n = s.size();
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '(')
{
leftsta.push(s[i]);
}
else if (s[i] == ')')
{
if (!leftsta.empty())
{
leftsta.pop();
}
else
{
del_rightnum++;
}
}
}
while (!leftsta.empty())
{
del_leftnum++;
leftsta.pop();
}
//cout << del_leftnum << " " << del_rightnum;
dfs(s, n, state, leftnum, rightnum, del_leftnum, del_rightnum, 0);
//cout << ans.size() << endl;
return ans;
}
};
成功做出的第二道困难题,其实这题我觉得应该就是一个比较难的中等题。
这道题的思路不难,一看到题目和样例就知道是回溯法,都是老套路了。这题比较关键的地方在于判断要删除几个左括号、几个右括号。
我一开始的想法是遍历一遍s,如果左括号比右括号多几个,就删除几个左括号,反之亦然,但是想了一下发现不对,例如对于 ")(" 这个样例,左括号和右括号数量相等,但很明显两个括号都应该删除掉,所以就要用一下辅助栈了:
每次遇到左括号 "(" 就入栈;遇到右括号 ")" 就将栈中弹出一个左括号表示两个括号匹配,如果栈是空的,那么就说明这个右括号不能匹配,于是我们就应该删除一个右括号;等遍历完之后,如果栈中还有左括号,那么就说明这些左括号是不能匹配的,所以待会就应该删除掉等量的左括号。
之后就是老套路dfs回溯了,这里有个比较重要的剪枝,下面的第二个条件如果去掉,那么将会有样例超时。
//前者表示一旦出现右括号数量大于左括号数量,那么一定是错误的
//后者是重要的剪枝,如果要删除的括号数量大于还剩的字符数量,那么可以直接返回
if (rightnum > leftnum || (del_leftnum + del_rightnum > n - index))
{
return;
}