题目描述
给你一个由若干括号和字母组成的字符串 s ,删除最小数量的无效括号,使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
样例1
输入:s = "()())()"
输出:["(())()","()()()"]
样例2
输入:s = "(a)())()"
输出:["(a())()","(a)()()"]
样例3
输入:s = ")("
输出:[""]
条件
-
1 <= s.length <= 25
-
s 由小写英文字母以及括号 ‘(‘ 和 ‘)’ 组成
-
s 中至多含 20 个括号
算法1
(dfs)
- 先预处理出符合条件的最短字符串长度
- 开始暴力搜索
Java 代码
class Solution {
static int max;
static List<String> list;
public List<String> removeInvalidParentheses(String s) {
int res=0,n=s.length(),sum=0;
list=new LinkedList<>();
for(int i=0;i<n;i++){
if(s.charAt(i)=='('){
res++;
}else if(s.charAt(i)==')'){
if(res==0){
sum++;
}else{
res--;
}
}
}
res+=sum;
res=s.length()-res;
max=res;
dfs(s,0,0,"");
return list;
}
static void dfs(String s,int res,int index,String str){
if(res<0) return;
if(str.length()>max) return;
if(index==s.length()){
if(str.length()==max&&res==0&&!list.contains(str)){
list.add(str);
}
return;
}
if(s.charAt(index)=='('){
dfs(s,res+1,index+1,str+s.charAt(index));
dfs(s,res,index+1,str);
}else if(s.charAt(index)==')'){
dfs(s,res-1,index+1,str+s.charAt(index));
dfs(s,res,index+1,str);
}else{
dfs(s,res,index+1,str+s.charAt(index));
}
}
}
算法2
(bfs)
Java 代码
class Solution {
public static List<String> removeInvalidParentheses(String s) {
List<String> list=new LinkedList<>();
if(s.length()==0) {
return list;
}
Queue<String> queue=new LinkedList<>();
Set<String> set=new HashSet<>();
queue.add(s);
set.add(s);
boolean flag=false;
while(!queue.isEmpty()) {
int size=queue.size();
for (int j = 0; j <size; j++) {
String poll = queue.poll();
if(check(poll)) {
flag=true;
list.add(poll);
}
for (int i = 0; i <poll.length(); i++) {
StringBuffer br=new StringBuffer(poll);
if(br.charAt(i)!='('&&br.charAt(i)!=')') {
continue;
}
String ss = br.deleteCharAt(i).toString();
if(!set.contains(ss)) {
set.add(ss);
queue.add(ss);
}
}
}
if(flag) {
break;
}
}
return list;
}
static boolean check(String s) {
char[] charArray = s.toCharArray();
int count = 0;
for (char c : charArray) {
if (c == '(') {
count++;
} else if (c == ')') {
count--;
}
if (count < 0) {
return false;
}
}
return count == 0;
}
}