301.删除无效的括号

题目：301.删除无效的括号

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。

示例：

输入：s = "()())()"
输出：["(())()","()()()"]

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

输入：s = ")("
输出：[""]

题解：

今天是一道括号匹配的题目，题目要求输出有效并且最长的字符串，所以没有别的方法，只能回溯搜索+剪枝，每次遇到括号都有两种情况，选和不选，遇到字母就放入字符串中，不过要先遍历一次给的字符串，确定要删除多少左括号和删除多少有括号，确定最终有效字符串的长度。

HashSet<String> help = new HashSet<>();
public List<String> removeInvalidParentheses(String s) {
    String s1 = "";
    int r = 0,l = 0;
    for (int i = 0;i<s.length();i++){
        if (s.charAt(i)=='(')
        	l++;     //l表示删除左括号的数量
        if (s.charAt(i)==')'){
            l--;
            if (l<0){
                r++;//r表示删除右括号的数量
                l = 0;
            }
        }
    }
    int x = t+l;   //x表示删除括号的总和
    dfs(s,0,0,s1,x);
    return new ArrayList<>(help);
}
public void dfs(String s,int index,int x,String s1,int t){
    if (index>=s.length()){
        if (x==0&&s1.length()==s.length()-t&&!help.contains(s1)){
        	help.add(s1);
        }
    	return ;
    }
    if (x<0){
    	return ;
    }
    if (s.charAt(index)=='('){
        dfs(s,index+1,x,s1,t);
        dfs(s,index+1,x+1,s1+"(",t);
    }else if (s.charAt(index)==')'){
        dfs(s,index+1,x,s1,t);
        dfs(s,index+1,x-1,s1+")",t);
    }else{
    	dfs(s,index+1,x,s1+s.charAt(index),t);
    }
}

下面是三叶大佬的方法，她在遍历的过程中进行了剪枝，所以效率要高很多，学习了！

Set<String> set = new HashSet<>();
int n,max,len;
String s;
public List<String> removeInvalidParentheses(String _s) {
    s = _s;
    n = s.length();
    int l = 0,r = 0;
    int c1 = 0,c2=0;
    for (char c:s.toCharArray()){
        if (c=='('){
            c1++;
            l++;
        }else if(c==')'){
            c2++;
            if (l!=0) l--;
            else r++;
        }
    }
    //l，r分别表示需要删除的左右括号的数量
    //len代表最终字符串的长度
    len = n-l-r;
//c1 c2 分别代表左/右括号的数量，要想做到括号匹配，最终匹配的数量等于少的那一个的数量
    max = Math.min(c1,c2);
    dfs(0,"",l,r,0);
    return new ArrayList<>(set);
}
public void dfs(int u,String cur,int l,int r,int score){
	//如果不符合要求了就直接返回，进行剪枝！！！加速操作！！！
    if (l<0||r<0||score<0||score>max) return ;
    if (l==0&&r==0){
    	//如果左右括号都删完了，并且长度也满足要求，就说明是有效字符串
    	if (cur.length()==len) set.add(cur);
    }
    //如果到了最后也没有满足要求，也返回
    if (u==n) return ;
    char c = s.charAt(u);
    if (c=='('){
        dfs(u+1,cur+String.valueOf(c),l,r,score+1);
        dfs(u+1,cur,l-1,r,score);
    }else if (c==')'){
        dfs(u+1,cur+String.valueOf(c),l,r,score-1);
        dfs(u+1,cur,l,r-1,score);
    }else
    	dfs(u+1,cur+String.valueOf(c),l,r,score);
}

后记：

今天第一次自己A出了困难题（虽然也不太难），但是也是值得庆祝的一天，这是向大佬迈出的第一步，开心！！！！