题目描述
题解思路
首先,这道题要求我们给出所有结果,那就意味着我们可能只能选择枚举这一条路,然后再看到数据范围,好家
伙,确实挺小的,然后我们可以发现,对于每个"(",和")",我们都有俩种选法,删或存,但是如果我们用DFS把所有
情况都枚举出来,那先不考虑时间问题,会不会DFS溢出都是疑问,所以必须要剪枝,那我们可以考虑一下,我们的
目标是什么?是让所有的“(”和“)”数量匹配,那么我们的删除操作就不能把情况复杂,而是要降低不匹配度,所以我
们可以计算该位置删除后不匹配度的变化来判断去留,从而进行简单的剪枝,虽然有进一步剪枝的方法,但我后面提
交发现这个程度已经可以了。
代码
class Solution {
int[][] pre_cal;
int unFitLeft = 0;
int unFitRight = 0;
List<String> ans = new ArrayList<>();
public int[] Calc(String s)
{
int nowUnFitLeft = 0;
int nowUnFitRight = 0;
int[] a = new int[2];
for(int i = 0;i < s.length(); i++)
{
if(s.charAt(i) == '(') nowUnFitLeft ++;
else if(s.charAt(i) == ')')
{
nowUnFitLeft --;
if(nowUnFitLeft < 0)nowUnFitLeft = 0;
}
}
for(int i = s.length() - 1;i >= 0; i--)
{
if(s.charAt(i) == ')') nowUnFitRight ++;
else if(s.charAt(i) == '(')
{
nowUnFitRight --;
if(nowUnFitRight < 0)nowUnFitRight = 0;
}
}
a[0] = nowUnFitLeft;
a[1] = nowUnFitRight;
return a;
}
public List<String> removeInvalidParentheses(String s) {
pre_cal = new int[s.length()+10][4];
for(int i = 0;i < s.length(); i++)
{
if(s.charAt(i) == '(') unFitLeft ++;
else if(s.charAt(i) == ')')
{
unFitLeft --;
if(unFitLeft < 0)unFitLeft = 0;
}
}
for(int i = s.length() - 1;i >= 0; i--)
{
if(s.charAt(i) == ')') unFitRight ++;
else if(s.charAt(i) == '(')
{
unFitRight --;
if(unFitRight < 0)unFitRight = 0;
}
}
find(s,0,unFitLeft,unFitRight);
return ans;
}
public void find(String now_ans,int k,int nowUnFitLeft,int nowUnFitRight)
{
int len = now_ans.length();
if(k >= len){
if(nowUnFitLeft == 0 && nowUnFitRight == 0)
if(!ans.contains(now_ans)) ans.add(now_ans);
return;
}
find(now_ans,k+1,nowUnFitLeft,nowUnFitRight);
if(now_ans.charAt(k) != '(' && now_ans.charAt(k) != ')')
return;
String now = now_ans.substring(0,k) + now_ans.substring(k + 1,len);
int[] now_sum = Calc(now);
if(now_sum[0] == 0 && now_sum[1] == 0)
{
if(!ans.contains(now)) ans.add(now);
return;
}
if(now_sum[0] <= nowUnFitLeft && now_sum[1] <= nowUnFitRight )
find(now,k,now_sum[0],now_sum[1]);
return;
}
}
结语
如果有想一起每天互相监督刷题的小伙伴可以加上微信,咱们一起加油呀!也可以一起讨论讨论题目
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)