301. 删除无效的括号（高频题）

- 日理万妓 2023-10-04 08:47 0阅读 0赞

#### 301. 删除无效的括号 ####

*  解题思路
 *  代码

## 解题思路 ##

要用**回溯算法**，一刷2021/3/19，没有完全弄明白

--------------------

最开始看到题目要求删除最小括号数目，我想的是dp，但是最后它要你返回的又是字符串的组合，所以就要回溯。  
整体思路比较简单：

1.  统计出来多余的左右括号
2.  进行回溯
3.  回溯中如果遇到多余的括号还没有全消除掉，那么就选择回溯消除
4.  如果对应的多余括号已经消除完了，那么就添加到`path`进行回溯

## 代码 ##

class Solution {
        
        // 用集合存储所有正确的字符串，可避免重复
        private Set<String> set = new HashSet<>();
    
        public List<String> removeInvalidParentheses(String s) {
        
            char[] ss = s.toCharArray();
            int open = 0, close = 0;
            // 获取应该去除的左右括号数
            for (char c : ss) {
        
                if (c == '(') {
        
                    open++;
                } else if (c == ')') {
        
                    if (open > 0) {
        
                        open--;
                    } else {
        
                        close++;
                    }
                }
            }
            // 回溯
            backTracking(ss, new StringBuilder(), 0, 0, 0, open, close);
            return new ArrayList(set);
        }
    
        public void backTracking(char[] ss, StringBuilder sb, int index, int open, int close, int openRem, int closeRem) {
        
            /**
             * 回溯函数
             * 分别对字符串中的每一位置的字符进行处理，最终获得符合要求的字符串加入集合中
             * @param ss 字符串对应的字符数组
             * @param sb 储存当前处理过且未去除字符的字符串
             * @param index 当前处理的字符位置
             * @param open 当前sb中储存的左括号数
             * @param close 当前sb中储存的右括号数
             * @param openRem 当前需要去除的左括号数
             * @param closeRem 当前需要去除的右括号数
             */
            // 所有字符都处理完毕
            if (index == ss.length) {
        
                // 如果应去除的左右括号数都变为0，则将sb插入set
                if (openRem == 0 && closeRem == 0) {
        
                    set.add(sb.toString());
                }
                return;
            }
            
            // 去掉当前位置的字符（括号），并处理下一个字符
            if (ss[index] == '(' && openRem > 0 || ss[index] == ')' && closeRem > 0) {
        
                
                if(ss[index] == '('){
        
                    backTracking(ss, sb, index + 1, open, close, openRem -  1 , closeRem);
                }
    
                if(ss[index] == ')'){
        
                    backTracking(ss, sb, index + 1, open, close, openRem  , closeRem -  1);
                }
                
           
            }
    
    
    
            // 不去掉当前位置字符
            // 将当前位置字符插入sb
            sb.append(ss[index]);
            // 当前位置不为括号，则直接处理下一个字符
            if (ss[index] != '(' && ss[index] != ')') {
        
                backTracking(ss, sb, index + 1, open, close, openRem, closeRem);
            }
            // 当前位置为左括号，增加左括号计数，处理下一个字符
            else if (ss[index] == '(') {
        
                backTracking(ss, sb, index + 1, open + 1, close, openRem, closeRem);
            }
            // 当前位置为右括号，且当前左括号计数大于右括号计数，则增加右括号计数，处理下一个字符
            else if (open > close) {
        
                backTracking(ss, sb, index + 1, open, close + 1, openRem, closeRem);
            }
            // 撤销选择
            sb.deleteCharAt(sb.length() - 1);
        }
    }