301. Remove Invalid Parentheses (Hard)

https://leetcode.com/problems/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 ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

Solutions

class Solution {

    // This is a brute force solution.

    // the minimum delete operations. Any outcome patterns the requires more than this is invalid.
    int minDelete = Integer.MAX_VALUE;

    public List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<>();

        if (s == null || s.length() == 0) {
            ans.add("");

            return ans;
        }

        minDelete = calculateMinDelete2(s);

        System.out.println(minDelete);

        recurse(s.toCharArray(), 0, "", ans, 0, 0, 0);

        if (ans.size() == 0) {
            ans.add("");
        }

        return ans;
    }

    private int calculateMinDelete(String s) {
        int invalidP = 0;

        int openP = 0;
        int closeP = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                openP++;
            }

            if (s.charAt(i) == ')') {
                closeP++;
            }

            if (openP < closeP) {
                openP = 0;
                closeP = 0;
                invalidP++;
            }
        }

        // do not forget the situation the the last char is open parenthese, say "(()("
        if (openP > closeP) {
            // be careful, not invalidP++;
            invalidP += openP - closeP;
        }

        return invalidP;
    }

    private int calculateMinDelete2(String s) {
        int invalidClose = 0;

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.add('(');

                continue;
            }

            if (s.charAt(i) == ')') {
                if (stack.isEmpty()) {
                    invalidClose++;
                } else {
                    stack.pop();
                }
            }
        }

        return invalidClose + stack.size();
    }

    private void recurse(char[] str, int start, String result, List<String> ans, int openP, int closeP, int delete) {
        if (delete > minDelete) {
            return;
        }

        // reach the end of the string
        if (start == str.length) {

            // invalid parentheses
            if (openP != closeP) {
                return;
            }

            // already covered pattern
            if (ans.contains(result)) {
                return;
            }

            ans.add(result);

            return;
        }

        // Open parentheses can never be less than close parentheses. Otherwise it is invalid parentheses string.
        if (openP < closeP) {
            return;
        }

        if (str[start] == '(') {
            recurse(str, start + 1, result + "(", ans, openP + 1, closeP, delete);

            recurse(str, start + 1, result, ans, openP, closeP, delete + 1);

            return;
        }

        if (str[start] == ')') {
            recurse(str, start + 1, result + ")", ans, openP, closeP + 1, delete);

            recurse(str, start + 1, result, ans, openP, closeP, delete + 1);

            return;
        }

        recurse(str, start + 1, result + str[start], ans, openP, closeP, delete);
    }
}

Incorrect Solutions

References