Remove Invalid Parentheses

题目地址：
https://leetcode.com/problems/remove-invalid-parentheses/#/description

题目：

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

解题思路：
要解决这道题，首先知道如何判断一连串的括号是不是valid的，这里用stack可以轻松实现；然后知道如何生成valid的括号对，这里用dfs就可以了；remove invalid parenthesis也是用dfs的思想，只不过需要keep更多的变量，leftCount和leftMax，并且要注意的是当是左括号的时候要先走保留的那一边，然后才是drop的那一支。最后当input用完了并且(leftCount匹配完成并且output不为空)之后，先更新global的max成maxLeft, 如果max==maxLeft并且没有重复，加进去结果。

代码：

checking if valid：

public boolean isValid(String s) {
    if(s == null || s.length() == 0){
        return false;
    }
    Deque<Character> stack = new ArrayDeque<Character>();
    for(int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if(c == '(' || c == '[' || c == '{'){
            stack.push(c);
        }
        else if(stack.isEmpty()){
            return false;
        }

        else if(c == ')' && stack.peek() == '('){
            stack.pop();
        }
        else if(c == ']' && stack.peek() == '['){
            stack.pop();
        }
        else if(c == '}' && stack.peek() == '{'){
            stack.pop();
        }
        else{
            return false;
        }
    }
    return stack.isEmpty();
}

generating valid parenthesis：

public List<String> generateParenthesis(int n) {
    List<String> rst = new ArrayList<>();
    if(n == 0){
        return rst;
    }
    helper(rst, n, n, new StringBuilder());
    return rst;
}
private void helper(List<String> rst, int left_remain, int right_remain, StringBuilder sb){
    if(left_remain == 0 && right_remain == 0){
        rst.add(sb.toString());
        return;
    }
    if(left_remain > 0){
        helper(rst, left_remain - 1, right_remain, sb.append("("));
        sb.deleteCharAt(sb.length() - 1);
    }
    if(left_remain < right_remain){
        helper(rst, left_remain , right_remain - 1, sb.append(")"));
        sb.deleteCharAt(sb.length() - 1);
    }
}

remove：

ArrayList<String> result = new ArrayList<String>();
int max=0;
public List<String> removeInvalidParentheses(String s) {
    if(s==null)
        return result;
    dfs(s, "", 0, 0);
    if(result.size()==0){
        result.add("");
    }
    return result;
}
public void dfs(String input, String output, int countLeft, int maxLeft){
    if(input.length()==0){
        if(countLeft==0 && output.length()!=0){
            if(maxLeft > max){
                max = maxLeft;
            }
            if(maxLeft==max && !result.contains(output)){
                result.add(output);
            }
        }
        return;
    }
    if(input.charAt(0)=='('){
        dfs(input.substring(1), output+"(", countLeft+1, maxLeft+1);//keep (        dfs(input.substring(1), output, countLeft, maxLeft);//drop (    }else if(input.charAt(0)==')'){
        if(countLeft>0){
            dfs(input.substring(1), output+")", countLeft-1, maxLeft);
        }
        dfs(input.substring(1), output, countLeft, maxLeft);
    }else{
        dfs(input.substring(1), output+String.valueOf(input.charAt(0)), countLeft, maxLeft);
    }
}