【LeetCode】301.删除无效的括号

题目

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= s.length <= 25
• s 由小写英文字母以及括号 '(' 和 ')' 组成
• s 中至多含 20 个括号

解答

源代码

class Solution {
    List res;
 
    public List removeInvalidParentheses(String s) {
        res = new ArrayList<>();
        int lremove = 0, rremove = 0;
 
        for (char c : s.toCharArray()) {
            if (c == '(') {
                lremove++;
            } else if (c == ')') {
                if (lremove > 0) {
                    lremove--;
                } else {
                    rremove++;
                }
            }
        }
 
        func(s, 0, lremove, rremove);
 
        return res;
    }
 
    public void func(String str, int start, int lremove, int rremove) {
        // 没有需要去掉的左右括号了
        if (lremove == 0 && rremove == 0) {
            if (isValid(str)) {
                res.add(str);
            }
 
            return;
        }
 
        for (int i = start; i < str.length(); i++) {
            if (i != start && str.charAt(i) == str.charAt(i  - 1)) {
                continue;
            }
 
            // 剩余的字符数量小于需要去掉的括号数，那就不符合，直接返回
            if (lremove + rremove > str.length() - i) {
                return;
            }
 
            if (lremove > 0 && str.charAt(i) == '(') {
                func(str.substring(0, i) + str.substring(i + 1), i, lremove - 1, rremove);
            }
 
            if (rremove > 0 && str.charAt(i) == ')') {
                func(str.substring(0, i) + str.substring(i + 1), i, lremove, rremove - 1);
            }
        }
    }
 
    public boolean isValid(String str) {
        int count = 0;
 
        for (char c : str.toCharArray()) {
            if (c == '(') {
                count++;
            } else if (c == ')') {
                count--;
 
                if (count < 0) {
                    return false;
                }
            }
        }
 
        return count == 0;
    }
}

总结

我们可以使用回溯算法，尝试遍历所有可能的去掉非法括号的方案。

先对原字符串进行统计，得到需要去掉的左右括号数量。然后我们尝试在原字符串中去掉这些数量的左右括号，检测剩余的字符串是否合法匹配，如果合法匹配则我们则认为该字符串为可能的结果，我们利用回溯算法来尝试搜索所有可能的去除括号的方案。

当需要去掉的左右括号的数量都为0时，判断此时的字符串是否匹配，若匹配则记录下来。

剩余字符数量小于当前左右括号数量时，可以直接判断字符串不符合，返回。

为了避免得到重复的结果，我们在每次进行搜索时，如果遇到连续相同的括号我们只需要搜索一次即可，比如当前遇到的字符串为 "(((())"，去掉前四个左括号中的任意一个，生成的字符串是一样的，均为 "((())"，因此我们在尝试搜索时，只需去掉一个左括号进行下一轮搜索，不需要将前四个左括号都尝试一遍。