给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()" 输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()" 输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25s由小写英文字母以及括号'('和')'组成s中至多含20个括号
Related Topics
类似广度优先搜索的处理办法、JAVA（详细注释）
括号字符串匹配问题我们常用的一个方法，遇到‘（’加1，遇到‘）’减1，结果为0的时候能表示形成完美匹配闭合。
这个问题也可以类比的想象为出入栈问题，‘（’入栈，‘）’出栈
另外，括号运算也可以类比的换算为其他结构，比如“树”
这是一个非常有意思的话题，不过题归正传，回到我们这题上
一顿分析
自己搞个字符串分析下看看，第二行标记的对应的映射关系，第三行统计了求和的值
( ( ) ( ) ) ) ) ( ) ) ( ( ( )
1 1 -1 1 -1 -1 -1 -1 1 -1 -1 1 1 1 -1
1 2 1 2 1 0 -1
当我们遇到这个和为-1的时候，很明显的说明了( ( ) ( ) ) )这段中有多余的)了，那么我们就把这段中的多余的)删掉一个再继续处理，可以得到如下两段，其中有一种连续的) )的情况删除任何一个结果都是一样的，这个可以再优化一下。
( ( ) ( ) )
( ( ( ) ) )
取第一种情况继续分析，那么字符串就变成了
( ( ) ( ) ) ) ( ) ) ( ( ( )
1 1 -1 1 -1 -1 -1 1 -1 -1 1 1 1 -1
1 2 1 2 1 0 -1
再次遇到了-1继续同样的操作，在所有的结果中我们再取其中一种，以下省略数步，得到其中一个如下结果
( ( ) ( ) ) ( ) ( ( ( )
1 2 1 2 1 0 1 0 1 2 3 2
最终的结果为2，这是另外一种情况，对应的我们应该往前删除两个(，但是前面的(很多，我们应该删除哪两个呢？
显然这个不能随意删除任意的(了，而是只能删除最后出现结果为0往后的位置中的(，但是这里面也有很多个(，又要删除哪两个呢？
最直观的办法当然是枚举所有的可能性，但是额外再写个枚举组合的算法好像有点麻烦，那么我们不如每个位置的(都删除一下，生成对应个数的字符串，然后再次处理整个逻辑，直到最后多余的(都处理掉的情况。
当然这里也直观的可以看到了重复( (的时候其实删除任意一个都是一样的，这个也许可以再优化一点点。
那么整个逻辑都清楚了，下面看代码，已经加了一点点额外的剪枝优化，
maxSize记录了已经得到的结果的最长长度，如果新的字符串比这个短就不用再处理了history记录了已经处理过的字符串的哈希表，如果已经处理过了就不用再处理这个了res结果先存入这个哈希表中，直接去重，防止有重复的结果被统计
代码
class Solution {
HashSet<String> history = new HashSet<>();
HashSet<String> res = new HashSet<>();
public List<String> removeInvalidParentheses(String s) {
Queue<String> queue = new LinkedList<>();
//加入一个队列待处理
queue.offer(s);
//maxSize 记录下当前得到的符合预期的结果中最长的结果的长度
int maxSize = 0;
while (!queue.isEmpty()){
String currentStr = queue.poll();
if (currentStr.length()<maxSize){
//如果这个字符串的长度已经小于可行结果中的最大长度，那么说明再处理之后得到的结果也不是最少删减个数能得到的
continue;
}
//下标标记
int idx = -1;
//遇到"("加1，遇到")"减1 遍历到idx位置的时候得到的结果
int total = 0;
//最有一个total等于0的时候的位置，后面有多余的"("的时候要用到
int lastZero = -1;
//判断是否遇到了total=-1的情况，其实也可以在下面修改flag = false;的地方用跳出外面一层循环的写法
boolean flag = true;
while (++idx < currentStr.length() && flag){
if (currentStr.charAt(idx) == '('){
//遇到'('加1
total++;
}
if (currentStr.charAt(idx) == ')'){
////遇到'('减1，其他都不用管
total--;
}
if (total==0){
//等于0的时候记录下最后0出现的位置
lastZero = idx;
}
//当到达某个下标的时候total=-1了，说明')'多了一个，需要在前面的所有')'中删除掉一个
if (total==-1){
//标记遇到-1的情况了
flag = false;
for (int i = 0; i <= idx; i++) {
//从头开始找')'
if (currentStr.charAt(i)==')'){
//删除掉指定位置的')'，生成新字符串
String tmpStr = strDeleteIndex(currentStr,i);
//如果没有处理过这种字符串的话，把他加入到queue、并标记为已经处理过这种的
if (!history.contains(tmpStr)){
history.add(tmpStr);
queue.add(tmpStr);
}
}
}
}
}
//如果没有遇到total=-1的情况，说明这里已经遍历到字符串的结尾了
if (flag){
//最终位置结果如果是大于0的，说明前面的lastZero位置到结束位置之间有多余的'('
if (total > 0){
//需要往前遍历找到最后一个0的位置lastZero从里面删除total个"("左括号，但是n个'('里面选total个'（'不是太好处理，需要组合不同情况
//那么我们就换一个简单点的办法，每个'('都删除一下，生成一个字符串，并重新执行上面的之前的逻辑，即把删除了一个'('的字符串
//重新加进queue再处理一遍，每次处理一个'('，直到最终处理掉了所有多余的'('
int i = lastZero;
while (++i < currentStr.length()){
if (currentStr.charAt(i) == '('){
//和上面处理')'一样，删除当前位置的'('，并加入到queue再次处理
String tmpStr = strDeleteIndex(currentStr,i);
if (!history.contains(tmpStr)){
history.add(tmpStr);
queue.add(tmpStr);
}
}
}
}else if (total == 0 && currentStr.length() >= maxSize){
//正好能闭合的添加进结果集，
//另外再判断更新maxSize，如果是长度比已有结果短的字符串就不用处理了
maxSize = currentStr.length();
res.add(currentStr);
}
}
}
List<String> l = new ArrayList<>();
int finalMaxSize = maxSize;
res.forEach(str->{
if (str.length()== finalMaxSize){
//再判断一遍长度，这边我也不确定是不是需要，所以保险起见还是写下吧
l.add(str);
}
});
return l;
}
/**
* 删除字符串指定下标位置的字符的封装方法，返回一个新的删除了指定位置的字符的字符串
* 由于调用的地方已经严格控制的idx不会越界，所以idx的越界问题就没有做判断处理
* @param str 原始字符串
* @param idx 待删除位置下标
* @return 新的删除了指定位置字符的字符串
*/
public String strDeleteIndex (String str, int idx){
char[] arr = new char[str.length()-1];
char[] origin = str.toCharArray();
System.arraycopy(origin,0,arr,0,idx);
System.arraycopy(origin,idx+1,arr,idx,arr.length-idx);
return new String(arr);
}
}
发表评论