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

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

一刷
题解：如果这个string不满足条件，那么出去其中的一个char, 并全部入栈，如果是6个char的时候满足条件，最终在队列中只会是6个和5个char, 由于found此时已被置为ture,那么就不会再往队列里面加入新的更短的字符串，可以保证Remove the minimum number

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        
        if(s == null) return res;
        
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        
        //initialize
        queue.add(s);
        visited.add(s);
        
        boolean found = false;
        
        while(!queue.isEmpty()){
            s = queue.poll();
            
            if(isValid(s)){
                res.add(s);
                found = true;
            }
            
            if(found) continue;
            
            //generate all possible states
            for(int i=0; i<s.length(); i++){
                if (s.charAt(i) != '(' && s.charAt(i) != ')') continue;
                
                String t = s.substring(0, i) + s.substring(i+1);//remove the ith
                
                if(!visited.contains(t)){
                    queue.add(t);
                    visited.add(t);
                }
            }
        }
        return res;
    }
    
    private boolean isValid(String s){
        int count = 0;
        for(int i = 0; i<s.length(); i++){
            char c = s.charAt(i);
            if(c == '(') count++;
            if(c == ')' && count-- ==0) return false;
        }
        return count == 0;
    }
}