LeetCode301：删除无效的括号

要求

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。

要求

方法：DFS 实现回溯搜索+剪枝
首先我们令左括号的得分为 1；右括号的得分为 −1。则会有如下性质：

• 对于一个合法的方案而言，必然有最终得分为 0；
• 搜索过程中不会出现得分值为 负数 的情况（当且仅当子串中某个前缀中「右括号的数量」大于「左括号的数量」时，会出现负数，此时不是合法方案）。

可以预处理搜索过程的最大得分： max = min(左括号的数量, 右括号的数量)

---

出现字符分三种情况：

• 左括号：如果增加当前 ( 后，仍为合法子串（即 score + 1 <= max) 时，我们可以选择添加该左括号，也能选择不添加；
• 右括号：如果增加当前 ) 后，仍为合法子串（即 score - 1 >= 0) 时，我们可以选择添加该右括号，也能选择不添加；
• 普通字符：直接添加。

使用 Set 进行方案去重，我们可以通过预处理，得到最后的「应该删除的左括号数量」和「应该删掉的右括号数量」，来直接得到最终的 len；考虑增加一层剪枝；
这里代码注释我也不能保证百分百准确，每个人理解的都不一样

class Solution {
    Set<String> set = new HashSet<>();
    // n：字符串长度；max：最大括号数（单括号）:maxPathLen：记录搜索过程中的最大路径子串的长度
    int n, max, maxPathLen;
    String s;

    public List<String> removeInvalidParentheses(String s) {
        n = s.length();
        int left = 0, right = 0;

        // 统计多余的括号数量
        for (char c : s.toCharArray()) {
            if (c == '(') left++;
            else if (c == ')') {
                if (left != 0) left--;
                else right++;
            }
        }
        maxPathLen = n - left - right;      // 提前更新 maxPathLen

        // 统计左右括号数量
        int left2 = 0, right2 = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') left2++;
            else if (c == ')') right2++;
        }

        max = Math.min(left2, right2);
        dfs(0, "", left, right, 0);
        return new ArrayList<>(set);    // 将Set集合转为List返回
    }

    /**
     * 遍历 _s 字符串，记录有效路径
     * @param curCharIndex 当前遍历的字符下标
     * @param path 遍历时的路径（括号组合字符串）
     * @param left 多余的左括号数量
     * @param right 多余的右括号数量
     * @param score 分数，用于标记左右括号的得分
     */
    private void dfs(int curCharIndex, String path, int left, int right, int score) {
        // 剪枝：合法路径的得分范围为 0 <= score <= max；多余的括号数量为负数，说明删多了，不符合
        if (left < 0 || right < 0 || score < 0 || score > max) return;

        if (left == 0 && right == 0) {
            // 多余的括号为0，且当前路径长度等于最大路径子串的长度，则符合
            if (path.length() == maxPathLen) {
                set.add(path);
            }
        }

        if (curCharIndex == n) return;      // 搜索完毕，退出（放在此处是为了记录完最后一个字符）

        char c = s.charAt(curCharIndex);     // 获取当前字符

        // 每一种选择都对应 添加/不添加
        if (c == '(') {         // 添加左括号，score + 1；不添加score不变，多余的左括号数量-1
            dfs(curCharIndex + 1, path + c, left, right, score+ 1);
            dfs(curCharIndex + 1, path, left - 1, right, score);
        } else if (c == ')') {      // 添加右括号，score - 1；不添加score不变，多余的右括号数量-1
            dfs(curCharIndex + 1, path + c, left, right, score - 1);
            dfs(curCharIndex + 1, path, left, right - 1, score);
        } else {        // 普通字符，score不变
            dfs(curCharIndex + 1, path + c, left, right, score);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

时间复杂度：预处理 max 和 len 的复杂度为 O(n)；不考虑 score带来的剪枝效果，最坏情况下，每个位置都有两种选择，搜索所有方案的复杂度为 O(2^ n )；同时搜索过程中会产生的新字符串（最终递归树中叶子节点的字符串长度最大为 n，使用 StringBuilder 也是同理），复杂度为O(n)。整体复杂度为 O(n * 2^n)
空间复杂度：最大合法方案数与字符串长度呈线性关系。复杂度为 O(n)

---

---

简化：从前往后删除多余右括号，从后往前删除多余左括号

public class LeetCode301 {
    public List<String> removeInvalidParentheses(String s) {
        int n = s.length();
        Set<String> set = new HashSet<>();
        dfs(s,set);
        //空的返回空字符串集合
        if (set.isEmpty()){
            set.add("");
        }
        return new ArrayList<>(set);
    }

    private void dfs(String s, Set<String> set) {
        //从左往右删除多余的右括号
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //count计数，左括号+1，右括号-1；
            if (c == '('){
                count++;
            }
            if (c == ')'){
                count--;
            }
            //count<0说明右括号富裕了，进行剪枝
            if (count < 0){
                for (int j = 0; j <= i; j++) {
                    //除第一个字符是'('时，遍历到j位置的前一个字符就是右括号，进行下个for循环，不行下面的语句
                    if (j > 0 && s.charAt(j-1) == ')'){
                        continue;
                    }
                    //如果当前位置就是右括号，剪枝，递归
                    if (s.charAt(j) == ')'){
                        //创建s字符串对象，可变的，deleteCharAt(j)删除当前索引位j的字符
                        dfs(new StringBuilder(s).deleteCharAt(j).toString(),set);
                    }
                }
                return;
            }
            //遍历到最后一位并且符合有效的括号，在进行添加返回
            if (i == s.length() - 1 && count == 0){
                set.add(s);
                return;
            }
        }

        //从右往左删除多余的左括号
        count = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == '(') count --;
            if (c == ')') count ++;
            //count < 0，说明左括号富裕了，进行剪枝
            if (count < 0){
                for (int j = s.length() - 1; j >= i; j--) {
                    //除最后一个字符是'('时，判断当前位置的下一个字符是否是'('，进行下次循环
                    if (j < s.length() - 1 && s.charAt(j + 1) == '('){
                        continue;
                    }
                    if (s.charAt(j) == '('){
                        dfs(new StringBuilder(s).deleteCharAt(j).toString(),set);
                    }
                }
                return;
            }
            //遍历到首位，如果符合有效括号
            if (i == 0 && count == 0){
                set.add(s);
                return;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73