​301. 删除无效括号

示例 1:

输入: "()())()"
输出: ["()()()", "(())()"]
示例 2:

输入: "(a)())()"
输出: ["(a)()()", "(a())()"]
示例 3:

输入: ")("
输出: [""]
 

示例 1：

输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：

输入：s = ")("
输出：[""]

void dfs(){
    // 终止条件，将中间结果集加入最终结果集
    // 遍历所有的选择
    // 回退当前的选择
}

    // index 当前遍历的下标
    // leftCount 已经遍历的左括号的数量
    // rightCount 已经遍历的右括号的数量
    // leftRemoveCount 最少应该删除的左括号的数量
    // rightRemoveCount 最少应该删除的右括号的数量
    // path 中间结果
    private void dfs(int index, int leftCount, int rightCount, int leftRemoveCount, int rightRemoveCount, StringBuilder path){

        // 终止条件,遍历的下标到达末尾，最少应该删除的左括号数量为0，而且最少应该删除的右括号数量为0
        if (index == len) {
            if (leftRemoveCount == 0 && rightRemoveCount == 0) {
                result.add(path.toString());
            }
            return;
        }
        // 当前字符串
        char currentChar = charArray[index];
        // 可能的操作1 删除当前的字符
        // 当前字符为左括号，index+1，leftRemoveCount(最少应该删除的右括号的数量)-1
        if(currentChar == '(' && leftRemoveCount > 0) {
            dfs(index + 1, leftCount, rightCount, leftRemoveCount - 1, rightRemoveCount, path);
        }
        // 当前字符为右括号，index+1，rightRemoveCount(最少应该删除的右括号的数量)-1
        if (currentChar == ')' && rightRemoveCount > 0) {
            dfs(index + 1, leftCount, rightCount, leftRemoveCount, rightRemoveCount - 1, path);
        }
        // 可能的操作2将当前字符加入中间结果 
        path.append(currentChar);
        // 若当前字符不为左右括号，index+1
        if (currentChar != '(' && currentChar != ')') {
            dfs(index + 1, leftCount, rightCount, leftRemoveCount, rightRemoveCount, path);
        // 当前字符为左括号，index+1，leftCount(已经遍历的左括号数量)+1
        } else if (currentChar == '(') {
            dfs(index + 1, leftCount + 1, rightCount, leftRemoveCount, rightRemoveCount, path);
        // 当前为右括号而且右括号的数量小于左括号，则将右括号加入进来，index+1，rightCount(已经遍历的右括号的数量)+1   
        } else if (currentChar == ')' && rightCount < leftCount) {
            dfs(index + 1, leftCount, rightCount + 1, leftRemoveCount, rightRemoveCount, path);
        }
        // 回退
        path.deleteCharAt(path.length() - 1);
    }

class Solution {
    // 要求不重复，用HashSet存储
    private HashSet<String> result = new HashSet<>();
    // 输入的字符长度
    private int len;
    // 输入字符转化为数组
    private char[] charArray;
    public List<String> removeInvalidParentheses(String s) {

        this.len = s.length();
        this.charArray = s.toCharArray();
        int leftRemoveCount = 0;
        int rightRemoveCount = 0;
        // 计算要删除的左括号的数量和右括号数量
        for (char c : charArray){
            if (c == '(') {
                leftRemoveCount++;
            } else if (c == ')') {
                if (leftRemoveCount == 0) {
                    rightRemoveCount++;
                } 
                if (leftRemoveCount > 0) {
                    leftRemoveCount--;
                }
                
            }
        }
        dfs(0, 0, 0, leftRemoveCount, rightRemoveCount, new StringBuilder());
        return new ArrayList<>(this.result);
        
    }

    // index 当前遍历的下标
    // leftCount 已经遍历的左括号的数量
    // rightCount 已经遍历的右括号的数量
    // leftRemoveCount 最少应该删除的左括号的数量
    // rightRemoveCount 最少应该删除的右括号的数量
    // path 中间结果
    private void dfs(int index, int leftCount, int rightCount, int leftRemoveCount, int rightRemoveCount, StringBuilder path){

        // 终止条件
        if (index == len) {
            if (leftRemoveCount == 0 && rightRemoveCount == 0) {
                result.add(path.toString());
            }
            return;
        }

        // 可能的操作1 删除当前的字符
        char currentChar = charArray[index];
        if(currentChar == '(' && leftRemoveCount > 0) {
            dfs(index + 1, leftCount, rightCount, leftRemoveCount - 1, rightRemoveCount, path);
        }
        if (currentChar == ')' && rightRemoveCount > 0) {
            dfs(index + 1, leftCount, rightCount, leftRemoveCount, rightRemoveCount - 1, path);
        }
        // 可能的操作2将当前字符加入中间结果 
        path.append(currentChar);
        if (currentChar != '(' && currentChar != ')') {
            dfs(index + 1, leftCount, rightCount, leftRemoveCount, rightRemoveCount, path);
        } else if (currentChar == '(') {
            dfs(index + 1, leftCount + 1, rightCount, leftRemoveCount, rightRemoveCount, path);
        } else if (currentChar == ')' && rightCount < leftCount) {
            dfs(index + 1, leftCount, rightCount + 1, leftRemoveCount, rightRemoveCount, path);
        }
        // 回退
        path.deleteCharAt(path.length() - 1);
    }
}