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

Examples: "()())()" -> ["()()()", "(())()"] "(a)())()" -> ["(a)()()", "(a())()"] ")(" -> [""]

先思考一道简单一些的，如果去掉minimum这个限制，返回一个修改后valid的，要怎么做？ 我的思路是用一个counter，遇到做括号就+1，右括号就-1，invalid的情况有如下两种： 1） 遇到右括号的时候，没有左括号可以pop,namely counter is zero 2） 最后stack里面还剩左括号没有pop, namely counter is larger than zero 第一种情况skip掉这种右括号，第二种情况append counter个右括号 如果要求minimum remove，并返回一个结果呢？这就比较tricky了， O(n)时间复杂度的算法是从左到右扫一遍，再从右到左扫一遍，用一个counter，删掉遇到的不合法的‘右’括号，这样我们就尽可能保留了左括号，从而保证minimum删除操作。

//)(())(
    public String oneValid(String s){
        int counter = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (c == '('){
                counter++;
            }
            if (c == ')'){
                counter--;
                if (counter < 0){
                    counter = 0;
                    continue;
                }
            }
            sb.append(c);
        }
        counter = 0;
        //(())(
        s = sb.toString();
        sb = new StringBuilder();
        for (int i = s.length() - 1; i >= 0; i--){
            char c = s.charAt(i);
            if (c == '('){
                counter--;
                if (counter < 0){
                    counter = 0;
                    continue;
                }
            }
            if (c == ')'){
                counter++;
            }
            sb.append(c);
        }
        return sb.reverse().toString();
    }

再进一步，如果要返回所有valid的结果呢？ 我觉得应该是用backtracking Now, we back to our original problem which aims to find the valid expression with minimum removals. Treat this as a graph. Each node on graph represents the current state after modification on its parent node. Then this problem is transformed to getting shortest path(s) on a graph. Obviously, BFS is the right track. Note, we should avoid duplicate state like we usually have a visited array to mark the nodes we explored. Same here, otherwise, the program will get TLE.

public List<String> minimum(String s){
  if (s == null) return new ArrayList<String>();
  Queue<String> Q = new LinkedList<String>();
  Set<String> set = new HashSet<>();
  List<String> res = new ArrayList<>();
  set.add(s);
  Q.offer(s);
  boolean found = false;//must be defined out of the while loop
  while (!Q.isEmpty()){
    int size = Q.size();
    for (int i = 0; i < size; i++){
      String tmp = Q.poll();      
      if (isValid(tmp)){
        res.add(tmp);
        found = true;
      }
      for (int j = 0; j < tmp.length(); j++){
        if (found) break;
         char e = tmp.charAt(j);
         StringBuilder sb = new StringBuilder(tmp);
         if (e == '(' || e == ')'){
           sb.deleteCharAt(j);
         }
         if (!set.contains(sb.toString())){           
           set.add(sb.toString());
           Q.offer(sb.toString());
         }
      }
    }
    if (found) return res;
  }
  return res;
}

private boolean isValid(String s){
  int counter = 0;
  for (int i = 0; i < s.length(); i++){
    char c = s.charAt(i);
    if (c == '('){
      counter++;
    }
    if (c == ')'){
      counter--;
    }
    if (counter < 0) return false;
  }
  return counter == 0;
}