301.Remove Invalid Parentheses

1-BFS Level By Level

Learn How to Traversal the BSF Level by Level.

https://leetcode.com/problems/remove-invalid-parentheses/discuss/75032/

T(n) = n x C(n, n) + (n-1) x C(n, n-1) + … + 1 x C(n, 1) = n x 2^(n-1).

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        if(s == null)
            return res;
        Set<String> visited = new HashSet<>();
        Deque<String> queue = new ArrayDeque<>();

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

        boolean found = false;

        while(!queue.isEmpty()){
            int levelSize = queue.size();
            for(int i = 0; i < levelSize; i++){
                String cur = queue.poll();
                //Valid
                if(isValid(cur)){
                    found = true;
                    res.add(cur);
                }
                //Not Valid then delete
                //If we found one, we never go to next level
                if(!found){
                    for(int j = 0; j < cur.length(); j++){
                        char c = cur.charAt(j);
                        if(c != '(' && c != ')')
                            continue;
                        String newString = cur.substring(0, j) + cur.substring(j + 1);
                        if(!visited.contains(newString)){
                            queue.add(newString);
                            visited.add(newString);
                        }
                    }
                }
            }

            //If found in current level, then stop BFS
            if(found)
                break;
        }
        return res;
    }
    boolean isValid(String s){
        int cnt = 0;
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == '(')
                cnt++;
            if(c == ')'){
                if(cnt == 0)
                    return false;
                cnt--;
            }
        }
        return cnt == 0;
    }
}

2-