题目描述

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

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

示例 1：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-invalid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

• 今天的算法的题目是括号类题目，这个题目把括号只限制在() 这一种括号，我们可以根据这一个条件简化处理的问题的思维和代码。

• 在有效的括号中，左括号出现的次数需要严格小于右括号出现的次数。我们首先遍历一次字符串s, 找出左右括号的差值。

• 接着，使用回溯来枚举所有的解。

通过代码

class Solution {
    private int len;
    private char[] charArray;
    private Set validExpressions = new HashSet<>();


    public List removeInvalidParentheses(String s) {
        this.len = s.length();
        this.charArray = s.toCharArray();
        int leftRemove = 0;
        int rightRemove = 0;
        for (char ch : charArray) {
            if (ch == '(') {
                leftRemove++;
            } else if (ch == ')') {
                if (leftRemove == 0) {
                    rightRemove++;
                } else if (leftRemove > 0) {
                    leftRemove--;
                }
            }
        }

        StringBuilder path = new StringBuilder();
        dfs(0, 0, 0, leftRemove, rightRemove, path);
        return new ArrayList<>(this.validExpressions);
    }

    public void dfs(int index, int leftCount, int rightCount, int leftRemove, int rightRemove, StringBuilder path) {
        if (index == len) {
            if (leftRemove == 0 && rightRemove == 0) {
                validExpressions.add(path.toString());
            }
            return;
        }

        char character = charArray[index];

        if (character == '(' && leftRemove > 0) {
            dfs(index + 1, leftCount, rightCount, leftRemove - 1, rightRemove, path);
        }

        if (character == ')' && rightRemove > 0) {
            dfs(index + 1, leftCount, rightCount, leftRemove, rightRemove - 1, path);
        }

        path.append(character);

        if (character != '(' && character != ')') {
            dfs(index + 1, leftCount, rightCount, leftRemove, rightRemove, path);
        } else if (character == '(') {
            dfs(index + 1, leftCount + 1, rightCount, leftRemove, rightRemove, path);
        } else if (rightCount < leftCount) {
            dfs(index + 1, leftCount, rightCount + 1, leftRemove, rightRemove, path);
        }

        path.deleteCharAt(path.length() - 1);
    }
}

总结

• 上述算法的时间复杂度是O(n * n), 空间复杂度是O(n)

• 坚持算法每日一题，加油！