网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 301. 删除无效的括号 ，难度为 困难。
Tag : 「括号问题」、「回溯算法」、「DFS」
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1:
输入: "()())()" 输出: ["()()()", "(())()"] 复制代码
.
示例 2:
输入: "(a)())()" 输出: ["(a)()()", "(a())()"] 复制代码
示例 3:
输入: ")(" 输出: [""] 复制代码
提示：
- 1 <= s.length <= 25
- s 由小写英文字母以及括号 '(' 和 ')' 组成
- s 中至多含 20 个括号
DFS 回溯算法
由于题目要求我们将所有（最长）合法方案输出，因此不可能有别的优化，只能进行「爆搜」。
我们可以使用 DFS 实现回溯搜索。
基本思路：
我们知道所有的合法方案，必然有左括号的数量与右括号数量相等。
首先我们令左括号的得分为 1；右括号的得分为 -1。那么对于合法的方案而言，必定满足最终得分为 0。
同时我们可以预处理出「爆搜」过程的最大得分： max = min(左括号的数量, 右括号的数量)
PS.「爆搜」过程的最大得分必然是：合法左括号先全部出现在左边，之后使用最多的合法右括号进行匹配。
枚举过程中出现字符分三种情况：
- 普通字符：无须删除，直接添加
- 左括号：如果当前得分不超过
max - 1时，我们可以选择添加该左括号，也能选择不添加 - 右括号：如果当前得大于 0（说明有一个左括号可以与之匹配），我们可以选择添加该右括号，也能选择不添加
使用 Set 进行方案去重，len 记录「爆搜」过程中的最大子串，然后将所有结果集中长度为 len 的子串加入答案：
class Solution { int len; public List<String> removeInvalidParentheses(String s) { char[] cs = s.toCharArray(); int l = 0, r = 0; for (char c : cs) { if (c == '(') { l++; } else if (c == ')') { r++; } } int max = Math.min(l, r); Set<String> all = new HashSet<>(); dfs(cs, 0, 0, max, "", all); List<String> ans = new ArrayList<>(); for (String str : all) { if (str.length() == len) ans.add(str); } return ans; } /** * cs: 字符串 s 对应的字符数组 * u: 当前决策到 cs 的哪一位 * score: 当前决策方案的得分值（每往 cur 追加一个左括号进行 +1；每往 cur 追加一个右括号进行 -1） * max: 整个 dfs 过程的最大得分 * cur: 当前决策方案 * ans: 合法方案结果集 */ void dfs(char[] cs, int u, int score, int max, String cur, Set<String> ans) { if (u == cs.length) { if (score == 0 && cur.length() >= len) { len = Math.max(len, cur.length()); ans.add(cur); } return; } if (cs[u] == '(') { if (score + 1 <= max) dfs(cs, u + 1, score + 1, max, cur + "(", ans); dfs(cs, u + 1, score, max, cur, ans); } else if (cs[u] == ')') { if (score > 0) dfs(cs, u + 1, score - 1, max, cur + ")", ans); dfs(cs, u + 1, score, max, cur, ans); } else { dfs(cs, u + 1, score, max, cur + String.valueOf(cs[u]), ans); } } } 复制代码
- 时间复杂度：不考虑 score 带来的剪枝效果，最坏情况下，每个位置都有两种选择。复杂度为 O(n * 2^n)O(n∗2n)
- 空间复杂度：最大合法方案数与字符串长度最多呈线性关系。复杂度为 O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.301 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
