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)

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)

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

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