【递归 回溯】LeetCode-301. 删除无效的括号

301. 删除无效的括号。

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

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

示例 1：

输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：

输入：s = ")("
输出：[""]

提示：

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

算法分析

解题思路
满足有效括号序列的性质

• 1、前缀序列中左括号的数量>=右括号的数量
• 2、左括号的数量=右括号的数量
  DFS

class Solution {List<String> res;public List<String> removeInvalidParentheses(String s) {res = new ArrayList<>();int l = 0;int r = 0;for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '(') {l++;}if (s.charAt(i) == ')') {if (l > 0) {l--;} else {r++;}}}dfs(s, 0, 0, l, r, "");return res;}public void dfs(String s, int u, int cnt, int l, int r, String path) {if (u == s.length()) {if (cnt == 0) {res.add(path);}return;}if (s.charAt(u) != '(' && s.charAt(u) != ')') {dfs(s, u + 1, cnt, l, r, path + s.charAt(u));} else {if (s.charAt(u) == '(') {int k = u;while (k < s.length() && s.charAt(k) == '(') {k++;}l -= k - u;for (int i = k - u; i >= 0; i--) {if (l >= 0) {dfs(s, k, cnt, l, r, path);}path += '(';l++;cnt++;}}if (s.charAt(u) == ')') {int k = u;while (k < s.length() && s.charAt(k) == ')') {k++;}r -= k - u;for (int i = k - u; i >= 0; i--) {if (cnt >= 0 && r >= 0) {dfs(s, k, cnt, l, r, path);}path += ')';r++;cnt--;}}}}
}

复杂性分析

时间复杂度：O(2^n * n)
空间复杂度：O(n)