算法-删除不匹配的括号描述
你将得到⼀个由⼩写字母a-z，左括号'('和右括号')'构成的字符串s。
你的任务是删除尽可能少的括号，使得s⾥⾯的括号匹配。
你需要返回删除括号后的字符串。
由于答案可能会有很多，所以你只需要返回任意⼀个正确答案。
例如："()", "(())", "()()", "(())()"是括号匹配的字符串，⽽")(", "(()", "()()(", "()())"则是括号不匹配的字符串。样例样例1：
输⼊：
s = "a(b(c(de)fgh)"
输出：
"a(b(cde)fgh)"
解释：
正确答案有三个："ab(c(de)fgh)"，"a(bc(de)fgh)"，"a(b(cde)fgh)"。
你只需要返回任何⼀个。
样例2：
输⼊：
s = "((("
输出：
""
解释：
空串也属于括号匹配的字符串。
代码：
/**
* @author Bodhi.Li
* @date 2022/1/11
**/
@Slf4j
public class Demo {
public static void main(String[] args) {
List<String> strings = removeInvalidParentheses("()())");
System.out.println(strings);字符串截取后面三位
}
public static List<String> removeInvalidParentheses(String s) {
int left = 0, right = 0;
char[] cs = s.toCharArray();
for(char c : cs) {
if(c == '(') {
left++;
}else if(c == ')') {
if(left == 0) right++;
else left--;
}
}
List<String> res = new ArrayList<>();
backtrace(cs, 0, new StringBuilder(s.length()-left-right), res, 0, 0, left, right);
return res;
}
private static void backtrace(char[] cs, int cur, StringBuilder sb, List<String> res,
int left, int right, int remL, int remR) {
if(cur == cs.length) {
if(remL == 0 && remR == 0) res.String());
return;
}
if(right > left) return;
final int len = sb.length();
if(cs[cur] == '(') {
/
/ use
sb.append('(');
backtrace(cs, cur+1, sb, res, left+1, right, remL, remR);
sb.setLength(len);
if(remL > 0) { // not use
while(cur < cs.length && cs[cur] == '(') { // find next
cur++;
remL--;
}
if(remL >= 0) backtrace(cs, cur, sb, res, left, right, remL, remR);            }
}else if(cs[cur] == ')') {
/
/ use
sb.append(')');
backtrace(cs, cur+1, sb, res, left, right+1, remL, remR);
sb.setLength(len);
if(remR > 0) { // not use
while(cur < cs.length && cs[cur] == ')') { // find next
cur++;
remR--;
}
if(remR >= 0) backtrace(cs, cur, sb, res, left, right, remL, remR);            }
}else {
sb.append(cs[cur]);
backtrace(cs, cur+1, sb, res, left, right, remL, remR);
sb.setLength(len);
}
}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。