网站开发湛江企业网站营销
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)