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())()"]
")(" -> [""]

Analysis

用BFS确保找到最短路径

Code

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<String>();
        if (s==null) return res;

        //Prepare queue and visited for BFS
        Queue<String> queue = new LinkedList<String>();
        Set<String> visited = new HashSet<String>();

        //initialize
        queue.add(s);
        visited.add(s);

        boolean found = false;

        while(!queue.isEmpty()){
            s = queue.poll();


            if(isValid(s)){
                res.add(s);
                found = true;
            }

            //一旦找到了一个s，只用处理queue里面和它同一level（或者小一level）的s即可，不用再删除字符了
            if(found) continue;

            //generate strings delete only one char
            for (int i=0; i<s.length(); i++){
                if (s.charAt(i)!='(' && s.charAt(i)!=')') continue;
                //删除t位置的char
                String t = s.substring(0,i)+s.substring(i+1);
                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 ch = s.charAt(i);
            if (ch=='(') count++;
            if (ch==')' && count--==0) return false;
        }
        return count==0;
    }
}

Reference

Leetcode