共计 3032 个字符，预计需要花费 8 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 301. 删除有效的括号 ，难度为 艰难。
Tag :「括号问题」、「回溯算法」、「DFS」
给你一个由若干括号和字母组成的字符串 s，删除最小数量的有效括号，使得输出的字符串无效。
返回所有可能的后果。答案能够按 任意程序 返回。
示例 1:
输出: "()())()"
输入: ["()()()", "(())()"]示例 2:
输出: "(a)())()"
输入: ["(a)()()", "(a())()"]示例 3:
输出: ")("
输入: [""]提醒：
- $1 <= s.length <= 25$
s由小写英文字母以及括号'('和')'组成s中至少含20个括号
搜寻 + 剪枝
因为题目要求咱们将所有（最长）非法计划输入，因而不可能有别的优化，只能进行「爆搜」。
咱们能够应用 DFS 实现回溯搜寻。
基本思路：
咱们晓得所有的非法计划，必然有左括号的数量与右括号数量相等。
首先咱们令左括号的得分为 $1$；右括号的得分为 $-1$。则会有如下性质：
- 对于一个非法的计划而言，必然有最终得分为 $0$；
- 搜寻过程中不会呈现得分值为 正数 的状况（当且仅当子串中某个前缀中「右括号的数量」大于「左括号的数量」时，会呈现正数，此时不是非法计划）。
同时咱们能够预处理出「爆搜」过程的最大得分：max = min(左括号的数量, 右括号的数量)
PS.「爆搜」过程的最大得分必然是：非法左括号先全副呈现在右边，之后应用最多的非法右括号进行匹配。
枚举过程中呈现字符分三种状况：
- 左括号：如果减少以后
(后，仍为非法子串（即 $score + 1 <= max$) 时，咱们能够抉择增加该左括号，也能抉择不增加； - 右括号：如果减少以后
)后，仍为非法子串（即 $score – 1 >= 0$) 时，咱们能够抉择增加该右括号，也能抉择不增加； - 一般字符：间接增加。
应用 Set 进行计划去重，$len$ 记录「爆搜」过程中的最大子串，而后只保留长度等于 $len$ 的子串。
代码：
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);
}
}
}- 工夫复杂度：预处理 $max$ 的复杂度为 $O(n)$；不思考 $score$ 带来的剪枝成果，最坏状况下，每个地位都有两种抉择，搜寻所有计划的复杂度为 $O(2^n)$；同时搜寻过程中会产生的新字符串（最终递归树中叶子节点的字符串长度最大为 $n$，应用
StringBuilder也是同理），复杂度为 $O(n)$。整体复杂度为 $O(n \times 2^n)$ - 空间复杂度：最大非法计划数与字符串长度呈线性关系。复杂度为 $O(n)$
搜寻 + 剪枝
在解法一，咱们是在搜寻过程中去更新最初的 $len$。
但事实上，咱们能够通过预处理，失去最初的「应该删除的左括号数量」和「应该删掉的右括号数量」，来间接失去最终的 $len$。
因而在此基础上，咱们能够思考多减少一层剪枝。
代码：
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);
}
}
}- 工夫复杂度：预处理 $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/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布