给你一个由若干括号和字母组成的字符串 s ,删除最小数量的无效括号,使得输入的字符串有效。
返回所有可能的结果。答案可以按任意顺序返回。
示例 1:
输入:s = “()())()”
输出:[“(())()”,“()()()”]
示例 2:
输入:s = “(a)())()”
输出:[“(a())()”,“(a)()()”]
示例 3:
输入:s = “)(”
输出:[“”]
提示:
1 <= s.length <= 25
s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
s 中至多含 20 个括号
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/remove-invalid-parentheses
(1)回溯
思路参考本题官方题解。
//思路1————回溯
public class Solution {
//存放所有可能的结果
List<String> res = new ArrayList<String>();
public List<String> removeInvalidParentheses(String s) {
int lremove = 0;
int rremove = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
lremove++;
} else if (s.charAt(i) == ')') {
if (lremove == 0) {
rremove++;
} else {
lremove--;
}
}
}
backtrace(s, 0, lremove, rremove);
return res;
}
public void backtrace(String str, int start, int lremove, int rremove) {
if (lremove == 0 && rremove == 0) {
if (isValid(str)) {
res.add(str);
}
return;
}
for (int i = start; i < str.length(); i++) {
if (i != start && str.charAt(i) == str.charAt(i - 1)) {
continue;
}
//剪枝操作:如果剩余的字符无法满足去掉的数量要求,直接返回
if (lremove + rremove > str.length() - i) {
return;
}
//尝试去掉一个左括号
if (lremove > 0 && str.charAt(i) == '(') {
backtrace(str.substring(0, i) + str.substring(i + 1), i, lremove - 1, rremove);;
}
//尝试去掉一个右括号
if (rremove > 0 && str.charAt(i) == ')') {
backtrace(str.substring(0, i) + str.substring(i + 1), i, lremove, rremove - 1);
}
}
}
//判断字符串 str 中的括号是否有效
public boolean isValid(String str) {
int cnt = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
cnt++;
} else if (str.charAt(i) == ')') {
cnt--;
if (cnt < 0) {
return false;
}
}
}
return cnt == 0;
}
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_43004044/article/details/125029726
内容来源于网络,如有侵权,请联系作者删除!