301. Remove Invalid Parentheses

,

Solution 1

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
class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int leftParentheses = 0;
        int maxPairs = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftParentheses++;
            } else if (c == ')') {
                if (leftParentheses > 0) {
                    leftParentheses--;
                    maxPairs++;
                }
            }
        }

        Set<String> resultSet = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        dfs(resultSet, sb, s, 0, 0, 0, maxPairs);
        return new ArrayList<>(resultSet);
    }

    private void dfs(Set<String> resultSet, StringBuilder sb, String s, int i, int leftParentheses, int rightParentheses, int maxPairs) {
        if (i == s.length()) {
            if (leftParentheses == rightParentheses && leftParentheses == maxPairs) {
                resultSet.add(sb.toString());
            }

            return;
        }

        char c = s.charAt(i);
        if (c == '(') {
            // choose
            if (leftParentheses < maxPairs) {
                sb.append(c);
                dfs(resultSet, sb, s, i + 1, leftParentheses + 1, rightParentheses, maxPairs);
                sb.deleteCharAt(sb.length() - 1);
            }

            // not choose
            dfs(resultSet, sb, s, i + 1, leftParentheses, rightParentheses, maxPairs);
        } else if (c == ')') {
            // choose
            if (leftParentheses > rightParentheses) {
                sb.append(c);
                dfs(resultSet, sb, s, i + 1, leftParentheses, rightParentheses + 1, maxPairs);
                sb.deleteCharAt(sb.length() - 1);
            }

            // not choose
            dfs(resultSet, sb, s, i + 1, leftParentheses, rightParentheses, maxPairs);
        } else {
            // c is english letter
            sb.append(c);
            dfs(resultSet, sb, s, i + 1, leftParentheses, rightParentheses, maxPairs);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

示例：

1
2
3
4
5
6
            ((()))
        /           \
删除 '('          保留 '('
    /    \             /    \
删除 '(' 保留 '('  删除 '(' 保留 '('
...             ...
  • 每个括号都产生 2 个选择 → 总分支接近 2^n
  • 只有到叶子节点（全部字符处理完）才知道是否合法
  • 大量中间状态是无效的，但依然被递归探索

Solution 2

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
class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int leftParentheses = 0, maxPairs = 0;
        int uselessLeftParentheses = 0, uselessRightParentheses = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftParentheses++;
            } else if (c == ')') {
                if (leftParentheses > 0) {
                    leftParentheses--;
                    maxPairs++;
                } else {
                    uselessRightParentheses++;
                }
            }
        }
        uselessLeftParentheses = leftParentheses;

        Set<String> resultSet = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        dfs(resultSet, sb, s, 0, 0, 0, maxPairs, uselessLeftParentheses, uselessRightParentheses);
        return new ArrayList<>(resultSet);
    }

    private void dfs(Set<String> resultSet, StringBuilder sb, String s, int i, int leftParentheses, int rightParentheses,
                     int maxPairs, int uselessLeftParentheses, int uselessRightParentheses) {
        if (uselessLeftParentheses < 0 || uselessRightParentheses < 0) {
            return;
        }

        if (i == s.length()) {
            if (leftParentheses == rightParentheses && leftParentheses == maxPairs) {
                resultSet.add(sb.toString());
            }

            return;
        }

        char c = s.charAt(i);
        if (c == '(') {
            // choose
            if (leftParentheses < maxPairs) {
                sb.append(c);
                dfs(resultSet, sb, s, i + 1, leftParentheses + 1, rightParentheses, maxPairs, uselessLeftParentheses, uselessRightParentheses);
                sb.deleteCharAt(sb.length() - 1);
            }

            // not choose
            dfs(resultSet, sb, s, i + 1, leftParentheses, rightParentheses, maxPairs, uselessLeftParentheses - 1, uselessRightParentheses);
        } else if (c == ')') {
            // choose
            if (leftParentheses > rightParentheses) {
                sb.append(c);
                dfs(resultSet, sb, s, i + 1, leftParentheses, rightParentheses + 1, maxPairs, uselessLeftParentheses, uselessRightParentheses);
                sb.deleteCharAt(sb.length() - 1);
            }

            // not choose
            dfs(resultSet, sb, s, i + 1, leftParentheses, rightParentheses, maxPairs, uselessLeftParentheses, uselessRightParentheses - 1);
        } else {
            // c is english letter
            sb.append(c);
            dfs(resultSet, sb, s, i + 1, leftParentheses, rightParentheses, maxPairs, uselessLeftParentheses, uselessRightParentheses);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

该解法相比上面的解法剪枝更彻底：

1
2
3
4
5
6
7
8
9
10
11
12
13
 ((()))
    |
保留 '('
    |
保留 '('
    |
保留 '('
    |
保留 ')'
    |
保留 ')'
    |
保留 ')'
  • 由于每层递归只允许删除多余的括号，无用分支在中途就剪掉
  • 搜索树非常“瘦”，分支远小于 2^n
  • 最终生成的结果都是最少删除的合法字符串

References

301. Remove Invalid Parentheses