回溯算法：删除无效的括号

301. 删除无效的括号

关于括号相关的其他问题可见 回溯算法：括号生成 和 秒杀所有括号类问题。本篇文章主要结合题目 删除无效的括号 总结「判断括号字符串是否有效」的条件，同时扩展出几种剪枝的策略

首先我们回顾一下如何判断一个由括号组成的字符串是否有效？？

第一种方法：维护一个只存放左括号的栈，详情可见 秒杀所有括号类问题 中第一个题目的解题思路

第二种方法：对于一个字符串s来说，s的任意一个子串[0...i]中，(的数量肯定大于或等于)的数量，详情可见 回溯算法：括号生成 中的优化思路

我发现在实际题目中，第二种判定方法用到的更多！！

暴力回溯

下面我们看一种暴力的回溯代码，没有任何剪枝的版本！！

​x
private int len = 0;
private Set<String> set = new HashSet<>();
private StringBuffer track = new StringBuffer();
public List<String> removeInvalidParentheses(String s) {
    backtrack(s, 0, 0, 0);
    return new ArrayList<>(set);
}
private void backtrack(String s, int index, int left, int right) {
    if (index == s.length()) {
        if (left == right) {
            if (track.length() > len) {
                set = new HashSet<>();
                set.add(track.toString());
                len = track.length();
            } else if (track.length() == len) {
                set.add(track.toString());
            }
        }
        return ;
    }
    // 根据第二种判定方法判断括号是否合法
    if (left < right) return ;

    char c = s.charAt(index);
    // 如果是字母，必须选
    if (Character.isLowerCase(c)) {
        track.append(c);
        backtrack(s, index + 1, left, right);
        track.deleteCharAt(track.length() - 1);
    } else {
        track.append(c);
        if (c == '(') {
            // 选择
            backtrack(s, index + 1, left + 1, right);
        } else if (c == ')') {
            // 选择
            backtrack(s, index + 1, left, right + 1);
        }
        track.deleteCharAt(track.length() - 1);

        // 不选
        backtrack(s, index + 1, left, right);
    }
}

剪枝思路

当删除的字符数量已经大于最少删除数量时，剪枝！！！

xxxxxxxxxx
// 剪枝 1 : len 为合法时的最大长度，不断的更新
if (deleteLeft + deleteRight > s.length() - len) return;

我们可以提前对数据进行一些预处理，得到「最大删除的右括号数量」「最大括号对数量」

为什么可以得到这两个量呢？这就要回到上面介绍的第二种判定方法！！

对于「最大删除的右括号数量」，在我们遍历所有括号时，如果某一个子串中右括号大于左括号，那我们必然需要删掉一个右括号，所以可以得到最大需要删除的右括号数量

对于「最大括号对数量」，当我们得到所有的左右括号数量后，最大括号对的数量即为Math.min(l, r)

xxxxxxxxxx
int l = 0, r = 0;
for (char c : s.toCharArray()) {
    if (c == '(') l++;
    else if (c == ')') {
        if (l > r) r++;
        // r >= l 时，需要删除一个 r，所以需要删除的右括号数量 +1
        else maxRemoveright++;
    }
}
// 获得最大括号对数量
maxPairs = Math.min(l, r);

// 剪枝 2 : 删除的右括号超过最大删除的右括号数量
if (deleteRight > maxRemoveright) return;
// 剪枝 3 : 保留的括号数量已经大于最大括号对数量
if (left > maxPairs || right > maxPairs) return ;

完整代码

xxxxxxxxxx
private int len = 0;
private int maxPairs = 0;
private int maxRemoveright = 0;
private int deleteLeft = 0;
private int deleteRight = 0;
private Set<String> set = new HashSet<>();;
private StringBuffer track = new StringBuffer();
public List<String> removeInvalidParentheses(String s) {
    int l = 0, r = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') l++;
        else if (c == ')') {
            if (l > r) r++;
            else maxRemoveright++;
        }
    }
    maxPairs = Math.min(l, r);
    backtrack(s, 0, 0, 0);
    return new ArrayList<>(set);
}
private void backtrack(String s, int index, int left, int right) {
    if (index == s.length()) {
        if (left == right) {
            if (track.length() > len) {
                set = new HashSet<>();
                set.add(track.toString());
                len = track.length();
            } else if (track.length() == len) {
                set.add(track.toString());
            }
        }
        return ;
    }
    // 左括号少于右括号
    if (left < right) return ;
    // 删除的括号数量已经比最大删除数量多
    if (deleteLeft + deleteRight > s.length() - len) return;
    // 删除的右括号超过最大删除的右括号数量
    if (deleteRight > maxRemoveright) return;
    // 保留的括号数量已经大于最大括号对数量
    if (left > maxPairs || right > maxPairs) return ;
    char c = s.charAt(index);
    // 如果是字母，必须选
    if (Character.isLowerCase(c)) {
        track.append(c);
        backtrack(s, index + 1, left, right);
        track.deleteCharAt(track.length() - 1);
    } else {
        track.append(c);
        if (c == '(') {
            // 选择
            backtrack(s, index + 1, left + 1, right);
        } else if (c == ')') {
            // 选择
            backtrack(s, index + 1, left, right + 1);
        }
        track.deleteCharAt(track.length() - 1);

        // 不选
        if (c == '(') deleteLeft++;
        else deleteRight++;
        backtrack(s, index + 1, left, right);
        if (c == '(') deleteLeft--;
        else deleteRight--;
    }
}

下面附一张优化过程的执行时间图，如下：