LC 301. 删除无效的括号

题目描述

这是 LeetCode 上的 301. 删除无效的括号 ，难度为 困难。

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

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

示例 1:

1
2
3
输入: "()())()"

输出: ["()()()", "(())()"]

示例 2:
1
2
3
输入: "(a)())()"

输出: ["(a)()()", "(a())()"]

示例 3:
1
2
3
输入: ")("

输出: [""]

提示：

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

搜索 + 剪枝

由于题目要求我们将所有（最长）合法方案输出，因此不可能有别的优化，只能进行「爆搜」。

我们可以使用 DFS 实现回溯搜索。

基本思路：

我们知道所有的合法方案，必然有左括号的数量与右括号数量相等。

首先我们令左括号的得分为 $1$；右括号的得分为 $-1$。则会有如下性质：

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

同时我们可以预处理出「爆搜」过程的最大得分： max = min(左括号的数量, 右括号的数量)

PS.「爆搜」过程的最大得分必然是：合法左括号先全部出现在左边，之后使用最多的合法右括号进行匹配。

枚举过程中出现字符分三种情况：

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

使用 Set 进行方案去重，$len$ 记录「爆搜」过程中的最大子串，然后只保留长度等于 $len$ 的子串。

Java 代码：

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
class Solution {
    Set<String> set = new HashSet<>();
    int n, max, len;
    String s;
    public List<String> removeInvalidParentheses(String _s) {
        s = _s;
        n = s.length();
        int l = 0, r = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') l++;
            else if (c == ')') r++;
        }
        max = Math.min(l, r);
        dfs(0, "", 0);
        return new ArrayList<>(set);
    }
    void dfs(int u, String cur, int score) {
        if (score < 0 || score > max) return ;
        if (u == n) {
            if (score == 0 && cur.length() >= len) {
                if (cur.length() > len) set.clear();
                len = cur.length();
                set.add(cur);
            }
            return ;
        }
        char c = s.charAt(u);
        if (c == '(') {
            dfs(u + 1, cur + String.valueOf(c), score + 1);
            dfs(u + 1, cur, score);
        } else if (c == ')') {
            dfs(u + 1, cur + String.valueOf(c), score - 1);
            dfs(u + 1, cur, score);
        } else {
            dfs(u + 1, cur + String.valueOf(c), score);
        }
    }
}

C++ 代码：
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
class Solution {
public:
    unordered_set<string> resSet;
    int n, maxv, lenv;
    string s;
    vector<string> removeInvalidParentheses(string _s) {
        s = _s;
        n = s.size();
        int l = 0, r = 0;
        for (char c : s) {
            if (c == '(') l++;
            else if (c == ')') r++;
        }
        maxv = min(l, r);
        lenv = 0;
        resSet.clear();
        dfs(0, "", 0);
        return vector<string>(resSet.begin(), resSet.end());
    }
    void dfs(int u, string cur, int score) {
        if (score < 0 || score > maxv) return;
        if (u == n) {
            if (score == 0 && cur.length() >= lenv) {
                if (cur.length() > lenv) resSet.clear();
                lenv = cur.length();
                resSet.insert(cur);
            }
            return;
        }
        char c = s[u];
        if (c == '(') {
            dfs(u + 1, cur + c, score + 1);
            dfs(u + 1, cur, score);
        } else if (c == ')') {
            dfs(u + 1, cur + c, score - 1);
            dfs(u + 1, cur, score);
        } else {
            dfs(u + 1, cur + c, score);
        }
    }
};

Python 代码：
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
class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        self.rset = set()
        self.n = len(s)
        l = r = 0
        for c in s:
            if c == '(':
                l += 1
            elif c == ')':
                r += 1
        self.maxv = min(l, r)
        self.lenv = 0
        self.s = s
        
        def dfs(u, cur, score):
            if score < 0 or score > self.maxv:
                return
            if u == self.n:
                if score == 0 and len(cur) >= self.lenv:
                    if len(cur) > self.lenv:
                        self.rset.clear()
                    self.lenv = len(cur)
                    self.rset.add(cur)
                return
            c = self.s[u]
            if c == '(':
                dfs(u + 1, cur + c, score + 1)
                dfs(u + 1, cur, score)
            elif c == ')':
                dfs(u + 1, cur + c, score - 1)
                dfs(u + 1, cur, score)
            else:
                dfs(u + 1, cur + c, score)
        
        dfs(0, "", 0)
        return list(self.rset) if self.rset else [""]

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

搜索 + 剪枝

在解法一，我们是在搜索过程中去更新最后的 $len$。

但事实上，我们可以通过预处理，得到最后的「应该删除的左括号数量」和「应该删掉的右括号数量」，来直接得到最终的 $len$。

因此在此基础上，我们可以考虑多增加一层剪枝。

Java 代码：

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
class Solution {
    Set<String> set = new HashSet<>();
    int n, max, len;
    String s;
    public List<String> removeInvalidParentheses(String _s) {
        s = _s;
        n = s.length();

        int l = 0, r = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                l++;
            } else if (c == ')') {
                if (l != 0) l--;
                else r++;
            }
        }
        len = n - l - r;
        
        int c1 = 0, c2 = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') c1++;
            else if (c == ')') c2++;
        }
        max = Math.min(c1, c2);

        dfs(0, "", l, r, 0);
        return new ArrayList<>(set);
    }
    void dfs(int u, String cur, int l, int r, int score) {
        if (l < 0 || r < 0 || score < 0 || score > max) return ;
        if (l == 0 && r == 0) {
            if (cur.length() == len) set.add(cur);
        }
        if (u == n) return ;
        char c = s.charAt(u);
        if (c == '(') {
            dfs(u + 1, cur + String.valueOf(c), l, r, score + 1);
            dfs(u + 1, cur, l - 1, r, score);
        } else if (c == ')') {
            dfs(u + 1, cur + String.valueOf(c), l, r, score - 1);
            dfs(u + 1, cur, l, r - 1, score);
        } else {
            dfs(u + 1, cur + String.valueOf(c), l, r, score);
        }
    }
}

C++ 代码：
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
class Solution {
public:
    unordered_set<string> resSet;
    int n, maxv, lenv;
    string s;
    vector<string> removeInvalidParentheses(string _s) {
        s = _s;
        n = s.size();
        int l = 0, r = 0;
        for (char c : s) {
            if (c == '(') {
                l++;
            } else if (c == ')') {
                if (l > 0) l--;
                else r++;
            }
        }
        lenv = n - l - r;
        int c1 = 0, c2 = 0;
        for (char c : s) {
            if (c == '(') c1++;
            else if (c == ')') c2++;
        }
        maxv = min(c1, c2);
        dfs(0, "", l, r, 0);
        return vector<string>(resSet.begin(), resSet.end());
    }
    void dfs(int u, string cur, int l, int r, int score) {
        if (l < 0 || r < 0 || score < 0 || score > maxv) return;
        if (l == 0 && r == 0) {
            if (cur.length() == lenv) resSet.insert(cur);
        }
        if (u == n) return;
        char c = s[u];
        if (c == '(') {
            dfs(u + 1, cur + c, l, r, score + 1);
            dfs(u + 1, cur, l - 1, r, score);
        } else if (c == ')') {
            dfs(u + 1, cur + c, l, r, score - 1);
            dfs(u + 1, cur, l, r - 1, score);
        } else {
            dfs(u + 1, cur + c, l, r, score);
        }
    }
};

Python 代码：
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
class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        self.rset = set()
        self.n = len(s)
        l = r = 0
        for c in s:
            if c == '(':
                l += 1
            elif c == ')':
                if l > 0:
                    l -= 1
                else:
                    r += 1
        self.lenv = self.n - l - r
        c1 = sum(1 for char in s if char == '(')
        c2 = sum(1 for char in s if char == ')')
        self.maxv = min(c1, c2)
        self.s = s

        def dfs(u, cur, l, r, score):
            if l < 0 or r < 0 or score < 0 or score > self.maxv:
                return
            if l == 0 and r == 0:
                if len(cur) == self.lenv:
                    self.rset.add(cur)
            if u == self.n:
                return
            c = self.s[u]
            if c == '(':
                dfs(u + 1, cur + c, l, r, score + 1)
                dfs(u + 1, cur, l - 1, r, score)
            elif c == ')':
                dfs(u + 1, cur + c, l, r, score - 1)
                dfs(u + 1, cur, l, r - 1, score)
            else:
                dfs(u + 1, cur + c, l, r, score)

        dfs(0, "", l, r, 0)
        return list(self.rset) if self.rset else [""]

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

最后

这是我们「刷穿 LeetCode」系列文章的第 No.301 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。