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

Solution:

The idea is to use BFS to search a valid output.

If the current input is invalid, we peel off one of the parenthesis of this input string (length becomes n - 1), and try all of them.

We also need a HashSet to record all the substring that has been offered into the queue so that we will not meet duplicate string.

Time complexity is O(n x 2ⁿ) and space complexity is O(2ⁿ).

The detail explanation can be found here: Share my Java BFS solution



Code:

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() == 0) {
            result.add("");
            return result;
        }
        Queue<String> queue = new LinkedList<>();
        HashSet<String> hash = new HashSet<>();
        boolean found = false;
        queue.offer(s);
        while (!queue.isEmpty()) {
            String str = queue.poll();
            if (isValid(str)) {
                result.add(str);
                found = true;
            }
            if (found) {
                continue;
            }
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                if (c == '(' || c == ')') {
                    String sub = str.substring(0, i) + str.substring(i + 1);
                    if (!hash.contains(sub)) {
                        queue.offer(sub);
                        hash.add(sub);
                    }
                }
            }
        }
        return result;
    }
    
    public boolean isValid(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                count++;
            }
            if (s.charAt(i) == ')') {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }
}