301. Remove Invalid Parentheses

Problem:

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 ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

Analysis:
用到reverse那个递归方法暂时没看懂，而且也超出我的能力范围了。现在暂时用left and right count的方法做，容易理解和实现。
1. Count number of left and right invalid parentheses.
    '()()))()': right is 2.  ')(': left is 1 and right is 1
2. Typical dfs, remove left first then remove right. '())', only remove the first invalid, even remove dup is the typical dfs way.

Solution:
The index pass by dfs is i not i + 1, because we removed char at i, then i becomes the prev i + 1.

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null) return res;
        int left = 0, right = 0;
        for(int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') left++;
            if (s.charAt(i) == ')' && left > 0) left--;
            else if (s.charAt(i) == ')' && left == 0) right++;
        }
        
        dfs(s, 0, left, right, res);
        return res;
    }
    
    private void dfs(String s, int index, int left, int right, List<String> res) {
        if (left == 0 && right == 0) {
            if (isValid(s)) 
                res.add(s);
            return;
        }
            
        for (int i = index; i < s.length(); i++) {
            if (i != index && s.charAt(i) == s.charAt(i - 1)) continue;
            if (s.charAt(i) == '(' && left > 0) {
                dfs(s.substring(0, i) + s.substring(i + 1), i, left - 1, right, res);
            }
            if (s.charAt(i) == ')' && right > 0) {
                dfs(s.substring(0, i) + s.substring(i + 1), i, left, right - 1, res);
            }
        }
    }
    
    private boolean isValid(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') count++;
            else if (s.charAt(i) == ')' && --count < 0) return false;
        }
        return count == 0;
    }
}