Remove Invalid Parentheses

Question

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: [“()()()”, “(())()”]

LeetCodeleetcode.com/problems/remove-invalid-parentheses

Solution

/*
@param: String s
@return: List<String>
Algorithm: 先求出s中左括号与右括号的不规则数，然后逐一进行dfs+backtracking    
*/
Set<String> result;
public List<String> removeInvalidParentheses(String s) {   
    result = new HashSet<>();
    int left = 0, right = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') {
            left++;
        }else if (c == ')') {
            if (left > 0) {
                left--;
            }else {
                right++;
            }
        }
    }
    dfs(0, left, right, s, new StringBuilder());
    return new ArrayList<>(result);
}

private void dfs(int pos, int left, int right, String s, StringBuilder cur) {        
    if (left < 0 || right < 0) {
        return;
    }
    
    if (pos == s.length()) {
        if (left == 0 && right == 0) {
            if (valid(cur.toString())) {
                result.add(cur.toString());
            }
        }
        return;
    }
    char c = s.charAt(pos);
    int len = cur.length();
    if (c != '(' && c != ')') {
        cur.append(c);
        dfs(pos+1, left, right, s, cur);
    }else if (c == '(') {
        dfs(pos+1, left-1, right, s, cur);
        cur.append(c);
        dfs(pos+1, left, right, s, cur);
    }else {
        dfs(pos+1, left, right-1, s, cur);
        cur.append(c);
        dfs(pos+1, left, right, s, cur);
    }
    cur.delete(cur.length()-1, cur.length());
}


private boolean valid(String sb) {
    int left = 0, right = 0;
    for (char c : sb.toCharArray()) {
        if (c == '(') {
            left++;
        }else if (c == ')') {
            if (left > 0) {
                left--;
            }else {
                right++;
            }
        }
        if (right > left) {
            return false;
        }
    }
    if (left > 0 || right > 0) {
        return false;
    }
    
    return true;
}