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<>();
  queue.add(s);
  visited.add(s);
  boolean found=false;
  while (!queue.isEmpty()) {
    String t=queue.poll();
    if (isValid(t)) {
      res.add(t);
      found=true;
    }
    if (found) {
      continue;
    }
    for (int i=0; i < t.length(); i++) {
      if (t.charAt(i) != '(' && t.charAt(i) != ')') {
        continue;
      }
      t=t.substring(0,i) + t.substring(i + 1);
      if (!visited.contains(t)) {
        queue.add(t);
        visited.add(t);
      }
    }
  }
  return res;
}

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 < > ( ) ; queue . add ( s ) ; visited . add ( s ) ; boolean found = false ; while ( ! queue . isEmpty ( ) ) { String t = queue . poll ( ) ; if ( isValid ( t ) ) { res . add ( t ) ; found = true ; } if ( found ) { continue ; } for ( int i = 0 ; i < t . length ( ) ; i ++ ) { if ( t . charAt ( i ) != '(' && t . charAt ( i ) != ')' ) { continue ; } t = t . substring ( 0 , i ) + t . substring ( i + 1 ) ; if ( ! visited . contains ( t ) ) { queue . add ( t ) ; visited . add ( t ) ; } } } return res ; }
bfs . take the string after removing one parentheses as a level . first add the original string given to a queue . then start bfs , each time poll a string from the queue . check if the polled string is valid , if its valid , we don ' t need to generate next level . if it ' s not , generate all possible strings for the next level by removing one parentheses . < p > note that once we found one valid string , we know the minimum number . no need to generate the next level anymore . we can also use a string set to avoid duplicate check on strings .
