Poison

301. Remove Invalid Parentheses

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

        int maxScore = Math.min(leftParentheses, rightParentheses);
        int maxLength = s.length() - extraLeftParentheses - extraRightParentheses;
        Set<String> resultSet = new HashSet<>();
        dfs(s, resultSet, "", 0, extraLeftParentheses, extraRightParentheses, 0, maxScore, maxLength);

        return new ArrayList<>(resultSet);
    }

    private void dfs(String s, Set<String> resultSet, String curr, int index, int extraLeftParentheses, int extraRightParentheses, int score, int maxScore, int maxLength) {
        if (extraLeftParentheses < 0 || extraRightParentheses < 0 || score < 0 || score > maxScore) {
            return;
        }

        if (extraLeftParentheses == 0 && extraRightParentheses == 0) {
            // 多余的括号刚好被抵消完，还需判断是否达到了最大长度，因为可能存在非括号字符
            if (curr.length() == maxLength) {
                resultSet.add(curr);
            }
        }

        if (index == s.length()) {
            return;
        }

        char c = s.charAt(index);
        if (c == '(') {
            // 保留当前左括号
            dfs(s, resultSet, curr + c, index + 1, extraLeftParentheses, extraRightParentheses, score + 1, maxScore, maxLength);
            // 不保留当前左括号，即将当前左括号丢弃
            dfs(s, resultSet, curr, index + 1, extraLeftParentheses - 1, extraRightParentheses, score, maxScore, maxLength);
        } else if (c == ')') {
            // 保留当前右括号
            dfs(s, resultSet, curr + c, index + 1, extraLeftParentheses, extraRightParentheses, score - 1, maxScore, maxLength);
            // 不保留当前右括号，即将当前右括号丢弃
            dfs(s, resultSet, curr, index + 1, extraLeftParentheses, extraRightParentheses - 1, score, maxScore, maxLength);
        } else {
            // 始终保留英文字符
            dfs(s, resultSet, curr + c, index + 1, extraLeftParentheses, extraRightParentheses, score, maxScore, maxLength);
        }
    }
}
Reference

301. Remove Invalid Parentheses