LeetCode-每日一题 301. 删除无效的括号 [Java实现]

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

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

        分析题目，要求返回所有可能的结果，这就需要我们对每一个可能的结果都要进行判断，基于此我们选择深度优先搜索算法。我们首先定义终止情况：

• 当给定字符串枚举完成时
• 当当前字符串中未匹配括号数超出最大限制时

        为实现第二种终止情况我们可以定义一个参数 score 用来储存未匹配括号数，我们规定当向当前字符串中添加一个 ( 时， ++score；当添加一个 ) 时， --score。则易得 dfs 过程中 socre 在 [0, maxCount] 区间内，其中 maxCount 为左括号数与右括号数间较小值。

        为了简化程序，我们认为对于任意的 ( / ) 都存在添加 / 不添加两种状态，都对其进行分支处理，并在添加数据时不断校验结果的合理性（因为可能出现 ["()", "((()))"] 这种情况，题目要求仅删除最小数量的括号，这使得我们需要额外维护一个遍历 maxLength）。

    private Set result;
    private char[] input;
    private int length, maxScore, maxLength;

    public List removeInvalidParentheses(String s) {
        this.result = new HashSet<>(1 << 2);
        this.input = s.toCharArray();
        this.length = input.length;
        int left = 0, right = 0;
        for (char c : input) {
            if (c == '(') ++ left;
            else if (c == ')') ++ right;
        }
        maxScore = Math.min(left, right);
        backtrace(0, 0, "");
        return new ArrayList<>(result);
    }

    public void backtrace(int index, int score, String builder) {
        if (score < 0 || score > maxScore) return;
        if (index == length) {
            if (score == 0 && builder.length() >= maxLength) {
                if (builder.length() > maxLength) {
                    result.clear();
                    maxLength = builder.length();
                }
                result.add(builder);
            }
            return;
        }
        char now = input[index];
        if (now == '(') {
            backtrace(index+1, score+1, builder + '(');
            backtrace(index+1, score, builder);
        } else if (now == ')') {
            backtrace(index+1, score-1, builder + ')');
            backtrace(index+1, score, builder);
        } else {
            backtrace(index+1, score, builder + now);
        }
    }