力扣 301 删除无效的括号

题意：给定一个字符串找出删除最少非法字符串的所有组合

思路：

1. 遍历括号，找出合法的括号个数
2. 利用递归，遍历每一个子串的位置，具体思路可见代码注释

思想：括号的处理

复杂度：时间O（nⁿ)，空间O(n)

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int l = 0;
        int legal = 0;
        for(int i=0;i<s.length();i++) {
            if(s.charAt(i) == '(') {
                l++;
            } else if(s.charAt(i) == ')' && l > 0) {
                legal++;
                l--;
            }
        }
        Set<String> res = new HashSet(); 
        get(legal, legal, 0, new StringBuilder(), res, s, 0);
        
        return new ArrayList<String>(res);
    }
    
    void get(int l, int r, int open, StringBuilder temp, Set<String> res, String s, int index) {
        // 合法的左右括号或者开口的括号小于0，那么返回
        if(l < 0 || r < 0 || open < 0)
            return;
        // 遍历完字符串，且合法的左右括号都用完，且没有开口的括号，把当前字符串加入结果
        if(l == 0 && r == 0 && open == 0 && index == s.length()) {
            res.add(temp.toString());
            return;
        }
        // 遍历完字符串返回
        if(index >= s.length()) {
            return;
        }
        // 获取当下字符
        char cur = s.charAt(index);
        // 记录stringbuilder的长度
        int len = temp.length();
        // 把当下字符加到stringbuilder里
        temp.append(cur);
        if(cur == '(') {
            // 如果结果中包含当前的左括号，那么下次递归时，合法的左括号减1，开口括号＋1，字符串后移一位
            get(l-1, r, open+1, temp, res, s, index+1);
            // 重置
            temp.setLength(len);
            // 如果结果中不包含当前的左括号，那么下次递归时，合法的左右括号和开口括号不变，字符串后移一位
            get(l, r, open, temp, res, s, index+1);
        } else if(cur == ')') {
            // 同上，换成右括号
            get(l, r-1, open-1, temp, res, s, index+1);
            temp.setLength(len);
            get(l, r, open, temp, res, s, index+1);
        } else {
            // 因为是非括号字符，所以合法的左右括号和开口括号不变，字符串后移一位
            get(l, r, open, temp, res, s, index+1);
        }
    }
}