Question

Formatted question description: https://leetcode.ca/all/301.html

 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 ).

 Example 1:

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

 Example 2:

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

 Example 3:

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

Algorithm

Use BFS to solve, put the given string into the queue, and then take it out to check whether it is legal

  • If legal, return directly
  • If it is illegal, traverse it, and remove the bracket characters to generate a new string for the characters in the left and right brackets encountered
    • If this string has not been encountered before, put it in the queue and use HashSet to record whether a string has appeared.

Perform the same operation on each element in the queue, and return to the empty set if no valid string is found until the queue is empty.

Code

Java

  • import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Set;
    
    public class Remove_Invalid_Parentheses {
    
        // reference: https://leetcode.com/problems/remove-invalid-parentheses/solution/
        class Solution_dfs {
    
            private Set<String> validExpressions = new HashSet<String>();
            private int minimumRemoved;
    
            private void reset() {
                this.validExpressions.clear();
                this.minimumRemoved = Integer.MAX_VALUE;
            }
    
            private void dfs(
                String s,
                int index,
                int leftCount,
                int rightCount,
                StringBuilder expression,
                int removedCount) {
    
                // If we have reached the end of string.
                if (index == s.length()) {
    
                    // If the current expression is valid.
                    if (leftCount == rightCount) {
    
                        // If the current count of removed parentheses is <= the current minimum count
                        if (removedCount <= this.minimumRemoved) {
    
                            // Convert StringBuilder to a String. This is an expensive operation.
                            // So we only perform this when needed.
                            String possibleAnswer = expression.toString();
    
                            // If the current count beats the overall minimum we have till now
                            if (removedCount < this.minimumRemoved) {
                                this.validExpressions.clear();
                                this.minimumRemoved = removedCount;
                            }
                            this.validExpressions.add(possibleAnswer);
                        }
                    }
                } else {
    
                    char currentCharacter = s.charAt(index);
                    int length = expression.length();
    
                    // If the current character is neither an opening bracket nor a closing one,
                    // simply recurse further by adding it to the expression StringBuilder
                    if (currentCharacter != '(' && currentCharacter != ')') {
                        expression.append(currentCharacter);
                        this.dfs(s, index + 1, leftCount, rightCount, expression, removedCount);
                        expression.deleteCharAt(length);
                    } else {
    
                        // Recursion where we delete the current character at 'index' and move forward to 'index+1'
                        this.dfs(s, index + 1, leftCount, rightCount, expression, removedCount + 1);
                        expression.append(currentCharacter);
    
                        // If it's an opening parenthesis, consider it and recurse
                        if (currentCharacter == '(') {
                            this.dfs(s, index + 1, leftCount + 1, rightCount, expression, removedCount);
                        } else if (rightCount < leftCount) {
                            // For a closing parenthesis, only recurse if right < left
                            this.dfs(s, index + 1, leftCount, rightCount + 1, expression, removedCount);
                        }
    
                        // Undoing the append operation for other recursions.
                        expression.deleteCharAt(length);
                    }
                }
            }
    
            public List<String> removeInvalidParentheses(String s) {
    
                this.reset();
                this.dfs(s, 0, 0, 0, new StringBuilder(), 0);
                return new ArrayList(this.validExpressions);
            }
        }
    
    
        public class Solution_bfs {
            public List<String> removeInvalidParentheses(String s) {
                List<String> res = new ArrayList<>();
    
                // sanity check
                if (s == null) return res;
    
                Set<String> visited = new HashSet<>();
                Queue<String> queue = new LinkedList<>();
    
                // initialize
                queue.add(s);
                visited.add(s);
    
                boolean found = false;
    
                while (!queue.isEmpty()) {
                    s = queue.poll();
    
                    if (isValid(s)) {
                        // found an answer, add to the result
                        res.add(s);
                        found = true;
                    }
    
                    if (found) continue; // continue to check all in queue, but no more new adding to queue
    
                    // generate all possible states
                    for (int i = 0; i < s.length(); i++) {
                        // we only try to remove left or right parent
                        if (s.charAt(i) != '(' && s.charAt(i) != ')') continue;
    
                        String t = s.substring(0, i) + s.substring(i + 1); // skip char at index=i
    
                        if (!visited.contains(t)) {
                            // for each state, if it's not visited, add it to the queue
                            queue.add(t);
                            visited.add(t);
                        }
                    }
                }
    
                return res;
            }
    
            // helper function checks if string s contains valid parantheses
            boolean isValid(String s) {
                int count = 0;
    
                for (int i = 0; i < s.length(); i++) {
                    char c = s.charAt(i);
                    if (c == '(') count++;
                    if (c == ')') count--;
                    if (count < 0) return false;
                }
    
                return count == 0;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/remove-invalid-parentheses/
    // Time: O(2^N)
    // Space: O(N)
    class Solution {
    public:
        vector<string> removeInvalidParentheses(string s) {
            int N = s.size();
            vector<int> right(N + 1);
            for (int i = N - 1; i >= 0; --i) right[i] = max(0, right[i + 1] + (s[i] == '(' || s[i] == ')' ? (s[i] == ')' ? 1 : -1) : 0));
            unordered_set<string> ans;
            string tmp;
            function<void(int, int)> dfs = [&](int i, int left) {
                if (i == N) {
                    if (left == 0) ans.insert(tmp);
                    return;
                }
                if (s[i] == '(') {
                    if (left + 1 > right[i + 1]) { // we can remove this '('
                        dfs(i + 1, left);
                    }
                    ++left;
                } else if (s[i] == ')') {
                    if (right[i] > left) { // we can remove this ')'
                        dfs(i + 1, left);
                    }
                    if (left > 0) {
                        --left;
                    } else return;
                } 
                tmp.push_back(s[i]);
                dfs(i + 1, left);
                tmp.pop_back();
            };
            dfs(0, 0);
            return vector<string>(begin(ans), end(ans));
        }
    };
    
  • class Solution(object):
      def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
    
        def isValid(s):
          stack = []
          for c in s:
            if c == "(":
              stack.append("(")
            elif c == ")":
              stack.append(")")
              if len(stack) >= 2 and stack[-2] + stack[-1] == "()":
                stack.pop()
                stack.pop()
          return len(stack)
    
        def dfs(s, res, cache, length):
          if s in cache:
            return
    
          if len(s) == length:
            if isValid(s) == 0:
              res.append(s)
              return
    
          for i in range(0, len(s)):
            if s[i] == "(" or s[i] == ")" and len(s) - 1 >= length:
              dfs(s[:i] + s[i + 1:], res, cache, length)
              cache.add(s[:i] + s[i + 1:])
    
        prepLeft = ""
        for i in range(0, len(s)):
          if s[i] == "(":
            prepLeft += s[i:]
            break
          elif s[i] != ")":
            prepLeft += s[i]
    
        prepRight = ""
        for i in reversed(range(0, len(prepLeft))):
          if prepLeft[i] == ")":
            prepRight += prepLeft[:i + 1][::-1]
            break
          elif prepLeft[i] != "(":
            prepRight += prepLeft[i]
    
        s = prepRight[::-1]
        length = len(s) - isValid(s)
        res = []
        cache = set()
        dfs(s, res, cache, length)
        return res
    
    

All Problems

All Solutions