删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。
说明: 输入可能包含了除 (
和 )
以外的字符。
示例 1:
输入: “()())()”
输出: ["()()()", “(())()”]
示例 2:
输入: “(a)())()”
输出: ["(a)()()", “(a())()”]
示例 3:
输入: “)(”
输出: [""]
思路与代码
剪枝回溯
时间复杂度 O(2^n)
class Solution {
int minDel = Integer.MAX_VALUE;
Set<String> res = new HashSet();
public List<String> removeInvalidParentheses(String s) {
dfs(s, s.length(), 0, new StringBuffer(),0, 0, 0);
return new ArrayList(res);
}
// s:原字符串
// len 字符串长度
// index:当前字符串索引
// sb:当前保留的字符串
// sb_len: Stringbuffer中的长度
// leftNum:保留字符串中还未匹配的左括号的个数
// delted 已经删除的字符个数
public void dfs(String s, int len, int index, StringBuffer sb, int sb_len ,int leftNum, int deleted) {
if (deleted > minDel) return; // 如果已经删除的数量大于了最小数量
if (leftNum > len - index) // 如果剩下的字符个数比左边还未匹配的左括号个数还少
return;
if (index == len) { // 字符串已经遍历完
if (deleted <= minDel) {
if (deleted < minDel) {
minDel = deleted;
res.clear();
}
res.add(new String(sb));
}
return;
}
if (s.charAt(index) == '(') {
dfs(s, len,index + 1, sb, sb_len, leftNum, deleted + 1); // 删去当前字符
sb.append('(');
dfs(s, len, index + 1, sb, sb_len + 1, leftNum + 1, deleted); //保留当前字符
sb.deleteCharAt(sb_len);
} else if (s.charAt(index) == ')') {
dfs(s, len, index + 1, sb, sb_len, leftNum, deleted + 1); // 删去当前字符
if (leftNum != 0) {
sb.append(')');
dfs(s, len, index + 1, sb, sb_len + 1, leftNum - 1, deleted); //保留当前字符
sb.deleteCharAt(sb_len);
}
}else {
sb.append(s.charAt(index));
dfs(s, len, index + 1, sb, sb_len + 1, leftNum, deleted); //保留当前字符
sb.deleteCharAt(sb_len);
}
}
}