301. Remove Invalid Parentheses

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: [""]

Solution

先计算出多余的左括号和右括号,然后枚举
注意点:如何去除重复

Complexity

Code

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int r = 0, l = 0;
        for(Character c : s.toCharArray()){
            if(c == '('){
                l++;
            }else if(c == ')'){
                if(l == 0) r++;
                else l--;
            }
        }
        
        List<String> res = new LinkedList<>();
        dfs(s, l, r, 0, res);
        return res;
        
    }
    public void dfs(String s, int l, int r, int start, List<String> res){
        if(l == 0 && r == 0 && isValid(s)){
            res.add(s);
            return;
        }
        
        
        for(int i = start; i < s.length(); i++){
            
            if(i > 0 && s.charAt(i) == s.charAt(i-1))
                continue; // remove duplicate
            
            StringBuilder sb = new StringBuilder(s);
            if(s.charAt(i) == '(' && l > 0){
                sb.deleteCharAt(i);
                dfs(sb.toString(), l-1, r, i, res);
            }else if(s.charAt(i) == ')' && r > 0){
                sb.deleteCharAt(i);
                dfs(sb.toString(), l, r - 1, i, res);
            }
            
        }
    }
    
    public boolean isValid(String s){
        int count = 0; // 做括号未匹配个数
        for(Character c : s.toCharArray()){
            if(c == '('){
                count++;
            }else if(c == ')'){
                if(count > 0)
                    count--;
                else
                    return false;
            }
        }
       
        return count == 0;
    }
}