301 Remove Invalid Parentheses

301. Remove Invalid Parentheses

1. Question

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

2. Implementation

(1) BFS

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

        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

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

        boolean minLevel = false;

        while (!queue.isEmpty()) {
            String curStr = queue.remove();

            if (isValid(curStr)) {
                minLevel = true;
                res.add(curStr);
            }

            if (minLevel) {
                continue;
            }

            for (int i = 0; i < curStr.length(); i++) {
                if (isParenthesis(curStr.charAt(i))) {
                    String nextStr = curStr.substring(0, i) + curStr.substring(i + 1);

                    if (!visited.contains(nextStr)) {
                        queue.add(nextStr);
                        visited.add(nextStr);
                    }
                }
            }
        }
        return res;
    }

    public boolean isParenthesis(char c) {
        return c == '(' || c == ')';
    }

    public boolean isValid(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                ++count;
            }
            else if (s.charAt(i) == ')') {
                --count;
            }

            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }
}

(2) DFS

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int removableLeftParen = 0, removableRightParen = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') {
                ++removableLeftParen;
            }
            else if (c == ')') {
                if (removableLeftParen > 0) {
                    --removableLeftParen;
                }
                else {
                    ++removableRightParen;
                }
            }
        }

        Set<String> res = new HashSet<>();
        StringBuilder parens = new StringBuilder();
        removeParenthesisByDFS(s, 0, removableLeftParen, removableRightParen, 0, parens, res);
        return new ArrayList<>(res);
    }

    public void removeParenthesisByDFS(String s, int pos, int removableLeftParen, int removableRightParen, int open, StringBuilder parens, Set<String> res) {
        if (removableLeftParen < 0 || removableRightParen < 0 || open < 0) {
            return;
        }

        if (pos == s.length()) {
            if (removableLeftParen == 0 && removableRightParen == 0 && open == 0) {
                res.add(parens.toString());
            }
            return;
        }

        char c = s.charAt(pos);
        int len = parens.length();

        if (c == '(') {
            // Remove it
            removeParenthesisByDFS(s, pos + 1, removableLeftParen - 1, removableRightParen, open, parens, res);
            // Use it
            removeParenthesisByDFS(s, pos + 1, removableLeftParen, removableRightParen, open + 1, parens.append(c), res);
        }
        else if (c == ')') {
            // Remove it
            removeParenthesisByDFS(s, pos + 1, removableLeftParen, removableRightParen - 1, open, parens, res);
            // Use it
            removeParenthesisByDFS(s, pos + 1, removableLeftParen, removableRightParen, open - 1, parens.append(c), res);
        }
        else {
            removeParenthesisByDFS(s, pos + 1, removableLeftParen, removableRightParen, open, parens.append(c), res);
        }

        parens.setLength(len);
    }
}

3. Time & Space Complexity

BFS: 时间复杂度: O(n * 2^n), isValid()需要花费O(n), 每个string的character有两种状态(remove/keep)， 总共有2^n种状态，所以时间复杂度是O(n * 2^n), 空间复杂度O(2^n)

DFS: 时间复杂度: O(2^n)， 空间复杂度O(2^n)