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 {

        int minRemoveCount = Integer.MAX_VALUE;
        Set<String> result = new HashSet<>();

        public List<String> removeInvalidParentheses(String s) {
            dfs(s, 0, 0, 0, 0, new StringBuilder());

            return new ArrayList<String>(this.result);
        }

        private void dfs(
            String s,
            int index,
            int leftCount,
            int rightCount,
            int removeCount,
            StringBuilder expression) {

            if (index == s.length()) {
                if (leftCount == rightCount) {
                    // find one possible result
                    if (removeCount == this.minRemoveCount) {
                        this.result.add(expression.toString());
                    } else if (removeCount < this.minRemoveCount) {
                        this.minRemoveCount = removeCount;
                        this.result.clear();
                        this.result.add(expression.toString());
                    }
                }
            } else {
                // 2 cases: remove current char, keep current char
                char current = s.charAt(index);

                if (current != '(' && current != ')') {
                    // regular char
                    expression.append(current);
                    dfs(s, index + 1, leftCount, rightCount, removeCount, expression);
                    expression.deleteCharAt(expression.length() - 1);
                } else {

                    // 1: remove it, no matter ( or )
                    dfs(s, index + 1, leftCount, rightCount, removeCount + 1, expression);

                    // 2: keep it
                    expression.append(current);

                    if (current == '(') {
                        dfs(s, index + 1, leftCount + 1, rightCount, removeCount, expression);
                    } else if (rightCount < leftCount) {
                        // it's )
                        dfs(s, index + 1, leftCount, rightCount + 1, removeCount, expression);
                    }

                    expression.deleteCharAt(expression.length() - 1);
                }
            }
        }
    }

    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;
        }
    }
}

All Problems

All Solutions