# 301.Remove-Invalid-Parentheses

## 301. Remove Invalid Parentheses

## 题目地址

<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: [""]
```

## 代码

### Approach #1 BFS

Time: `T(n)` = `n` x `C(n, n)` + `(n-1)` x `C(n, n-1)` + ... + `1` x `C(n, 1)` = `n` x `2^(n-1)`

```java
class Solution {
  public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
    if (s == null)        return res;
    Set<String> visited = new HashSet();
    Queue<String> queue = new LinkedList();

    queue.add(s);
    visited.add(s);
    boolean found = false;

    while (!queue.isEmtpy()) {
      s = queue.poll();

      if (isValid(s)) {
        res.add(s);
        found = true;
      }

      if (found) continue; // minimum removal

      for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) != '(' && s.charAt(i) != ')') 
          continue;
        String t = s.substring(0, i) + s.substring(i + 1);

        if (!visited.contains(t)) {
          queue.add(t);
          visited.add(t);
        }
      }
    }

    return res;
  }

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

### Approach #2 DFS

Time: `O(2^n)` Space: `O(n)`

```java
class Solution {
  public List<String> removeInvalidParentheses(String s) {
    List<String> ans = new ArrayList();
    dfs(s, ans, 0, 0, new char[]{'(', ')'});
    return ans;
  }

  private void dfs(String s, List<String> ans, int last_i, last_j, char[] par) {
    int stack = 0;
    for (int i = last_i; i < s.length; i++) {
      if (s.charAt(i) == par[0])    stack++;
      if (s.charAt(i) == par[1])    stack--;
      if (stack >= 0) {
        continue;
      } else {
        for (int j = last_j; j <= i; j++) {
        if (s.charAt(j) == par[1] 
            && (j == last_j || s.charAt(j - 1) != par[1])) {
// Recursion: iStart = i since we now have valid # closed parenthesis thru i. jStart = j prevents duplicates
            dfs(s.substring(0, j) + s.substring(j + 1), ans, i, j, par);
          }
        }
        return;
      }
    }

    // No invalid closed parenthesis detected. Now check opposite direction, or reverse back to original direction.
    String reversed = new StringBuilder(s).reverse().toString();
    if (par[0] == '(') {
      dfs(reversed, ans, 0, 0, new char[]{')', '('});
    } else {
      ans.add(reversed);
    }

  }
}
```

### Approach #3 Backtracing

```java
class Solution {

  private Set<String> validExpressions = new HashSet<String>();

  private void recurse(
      String s,
      int index,
      int leftCount,
      int rightCount,
      int leftRem,
      int rightRem,
      StringBuilder expression) {

    // If we reached the end of the string, just check if the resulting expression is
    // valid or not and also if we have removed the total number of left and right
    // parentheses that we should have removed.
    if (index == s.length()) {
      if (leftRem == 0 && rightRem == 0) {
        this.validExpressions.add(expression.toString());
      }

    } else {
      char character = s.charAt(index);
      int length = expression.length();

      // The discard case. Note that here we have our pruning condition.
      // We don't recurse if the remaining count for that parenthesis is == 0.
      if ((character == '(' && leftRem > 0) || (character == ')' && rightRem > 0)) {
        this.recurse(
            s,
            index + 1,
            leftCount,
            rightCount,
            leftRem - (character == '(' ? 1 : 0),
            rightRem - (character == ')' ? 1 : 0),
            expression);
      }

      expression.append(character);

      // Simply recurse one step further if the current character is not a parenthesis.
      if (character != '(' && character != ')') {

        this.recurse(s, index + 1, leftCount, rightCount, leftRem, rightRem, expression);

      } else if (character == '(') {

        // Consider an opening bracket.
        this.recurse(s, index + 1, leftCount + 1, rightCount, leftRem, rightRem, expression);

      } else if (rightCount < leftCount) {

        // Consider a closing bracket.
        this.recurse(s, index + 1, leftCount, rightCount + 1, leftRem, rightRem, expression);
      }

      // Delete for backtracking.
      expression.deleteCharAt(length);
    }
  }

  public List<String> removeInvalidParentheses(String s) {

    int left = 0, right = 0;

    // First, we find out the number of misplaced left and right parentheses.
    for (int i = 0; i < s.length(); i++) {

      // Simply record the left one.
      if (s.charAt(i) == '(') {
        left++;
      } else if (s.charAt(i) == ')') {
        // If we don't have a matching left, then this is a misplaced right, record it.
        right = left == 0 ? right + 1 : right;

        // Decrement count of left parentheses because we have found a right
        // which CAN be a matching one for a left.
        left = left > 0 ? left - 1 : left;
      }
    }

    this.recurse(s, 0, 0, 0, left, right, new StringBuilder());
    return new ArrayList<String>(this.validExpressions);
  }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/graph-search/301.remove-invalid-parentheses.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.