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())()"]")(" -> [""]
思路：BFS暴力解法
import java.util.ArrayList;import java.util.HashSet;import java.util.LinkedList;import java.util.List;import java.util.Queue;import java.util.Set;/* * BFS solution */public class Solution {    public List<String> removeInvalidParentheses(String s) {            	List<String> rst = new ArrayList<String>();    	    	Set<String> visited = new HashSet<String>();    	Queue<String> queue = new LinkedList<String>();    	Queue<String> queue2 = new LinkedList<String>();    	    	queue.add(s);    	visited.add(s);    	    	boolean found = false;    	while(!queue.isEmpty()) {    		String ss = queue.remove();    		    		if(isValid(ss)) {    			rst.add(ss);    			found = true;    		}    		    		if(!found) {    			for(int i=0; i<ss.length(); i++) {    				String t = ss.substring(0, i) + ss.substring(i+1);    				if(!visited.contains(t)) {    					queue2.add(t);    					visited.add(t);    				}    			}    		}    		    		if(queue.isEmpty()) {    			if(found)	break;    			queue = queue2;    			queue2 = new LinkedList<String>();    		}    		    	}    	    	return rst;    }            public boolean isValid(String s) {    	char[] cs = s.toCharArray();    	int cnt = 0;    	for(char c : cs) {    		if(c == '(')	cnt++;    		if(c == ')')	cnt--;    		if(cnt < 0)		return false;    	}    	return cnt == 0;    }}