# 301 Remove Invalid Parentheses

input是一個String，移除最少個括號讓括號是合法的，並把合法的結果存在List<String>中回傳。

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

• idea 1: 列出所有的可能、並一一檢查是否合法。寫一個bfs function，拜訪所有的可能性，和一個checkValidity function，檢查是否合法。

• Code:

  public class Solution {
      public List<String> removeInvalidParentheses(String s) {
          /*
          check validation: stack, push "(" to stack, pop when meet")"
          try all possibilities, and check validation. -> O(n^2)
          */
          List<String> list;
  
          if(checkValidity(s)){
              list = new ArrayList<>();
              list.add(s);
              return list;
          }
  
          Set<String> res = new HashSet<>();
          bfs(s, res);
          list = new ArrayList<String>(res);
          return list;
      }
  
      void bfs(String s, Set<String> res){
          Queue<String> queue = new LinkedList<>();
          queue.offer(s);
          while(!queue.isEmpty()){
              String sub = queue.poll();
              // if sub is shorter than items in res, then no need to do further check
              String first = "";
              for(String item : res){
                  first = item;
                  break;
              }
              if(sub.length() <= first.length()) break;
  
              for(int i=0; i<sub.length(); i++){
                  StringBuilder sb = new StringBuilder(sub);
                  sb.deleteCharAt(i);
                  String cur = sb.toString();
                  queue.offer(cur);
                  if(checkValidity(cur)){
                      res.add(cur);
                  }
              }
          }
      }
  
      public boolean checkValidity(String s){
          Stack<Character> stack = new Stack<>();
          for(int i=0; i<s.length(); i++){
              if(s.charAt(i) == '('){
                  stack.push('(');
              }else if(s.charAt(i) == ')'){
                  if(stack.isEmpty()) return false;
                  else    stack.pop();
              }
          }
  
          if(stack.isEmpty()) return true;
          return false;
      }
  }
  

  結果才到第63個case就TLC了...

• Optimization

  1. checkValidity(): 用stack比較佔空間，可以改成用一個int stack，當讀到(就stack++，讀到)就stack--
  2. main(): convert set to list. 可以在中間就用visited的set來判斷是否需要加入list。應該不用一開始就check s，在bfs會做。

  3. bfs():

  4. 從queue吐出後就check，邏輯較清楚。

  5. 若當下的s就已經valid，則不用拆分成更小單位，可以省去很多時間。
  6. 另外，在拆分的部分不要用StringBuilder，太佔空間。直接做substring比較省。
  7. 如果要移除的字元不是括號，跳過，因為不影響結果。

• code

  public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        /*
        check validation: stack, push "(" to stack, pop when meet")"
        try all possibilities, and check validation. -> O(n^2)
        */
        List<String> list = new ArrayList<>();
  
        bfs(s, list);
        return list;
    }
  
    void bfs(String s, List<String> res){
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(s);
        visited.add(s);
  
        boolean found = false;
  
        while(!queue.isEmpty()){
            s = queue.poll();
            //System.out.println(s);
            //若當下的s已經valid，就不用再拆分成更小單位。
            if(isValid(s)){
                res.add(s);
                found = true;
            }
  
            if(found) continue;
  
            for(int i=0; i<s.length(); i++){
                if (s.charAt(i) != '(' && s.charAt(i) != ')') continue;
                String sub = s.substring(0,i);
                sub += s.substring(i+1);
  
                if(!visited.contains(sub)){
                    queue.offer(sub);
                    visited.add(sub);
                }
            }
        }
    }
  
    public boolean isValid(String s){
        int stack = 0;
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == '('){
                stack++;
            }else if(s.charAt(i) == ')'){
                stack--;
                if(stack < 0) return false;
            }
        }
        return stack == 0;
    }
  }