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

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        //at 
        Queue<String > queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        List<String> res = new ArrayList<>();

        queue.offer(s);
        // if found in certain level(bfs), traverse all in the queue, don't go deeper.
        boolean found = false;
        while(!queue.isEmpty()){
            String t = queue.poll();
            if(isP(t)){
                res.add(t);
                found = true;
            }
            if(found) continue; // get all the valid ones from queue.

            for(int i=0; i< t.length(); i++){
                if(t.charAt(i) != '(' && t.charAt(i) != ')') continue;
                String nt = t.substring(0, i) + t.substring(i+1);
                if(!visited.contains(nt)){
                    queue.offer(nt);
                    visited.add(nt);
                }
            }
        }
        return res;
    }

    boolean isP(String s){
        int count =0;
        for(char c : s.toCharArray()){
            if(c == '(') count++;
            else if(c == ')' && count-- == 0 ) return false;
        }
        return count == 0;
    }
}

DFS the order of dfs matters, take "(" as example,

public class Solution {
    Set<String> res = new HashSet<>();
    public List<String> removeInvalidParentheses(String s) {
        int lM = 0;
        int rM = 0;
        for(char c : s.toCharArray()){
            if(c == '(') lM++;
            if(c == ')'){
                if(lM != 0) lM--;
                else rM++;
            }
        }

        dfs(s, 0, lM, rM, 0, new StringBuilder());

        return new ArrayList<>(res);
    }

    void dfs(String s, int k, int lM, int rM, int open, StringBuilder sb){
        if(k == s.length() && lM == 0 && rM==0 && open == 0){
            res.add(sb.toString());
            return;
        }
        if( k == s.length() || lM < 0 || rM < 0 || open < 0) return;
        int len = sb.length();

        if(s.charAt(k) == '('){
            dfs(s, k+1, lM-1, rM, open, sb);
            dfs(s, k+1, lM, rM, open+1, sb.append('('));

        }else if(s.charAt(k) == ')'){

            dfs(s, k+1, lM, rM-1, open, sb);
            dfs(s, k+1, lM, rM, open-1, sb.append(')'));
        }else{
            dfs(s, k+1, lM, rM, open, sb.append(s.charAt(k)));
        }

        sb.setLength(len);
    }
}

Why the following not working, StringBuilder is shared between all dfs instances, and the following code set the length to be longer than its need in the second line, then the error, you should use a String instance instead of StringBuilder

            dfs(s, k+1, lM, rM, open+1, sb.append('('));
            dfs(s, k+1, lM-1, rM, open, sb);