301. Remove Invalid Parentheses

Question

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

Thinking:

• This question can use dfs to solve, and this question can be divided into 2 parts:
  1. Find the minimun ‘(‘ number and ‘)’ number to delete.
  2. dfs: remove ‘)’ first and then remove ‘(‘.

     class Solution {
       public List<String> removeInvalidParentheses(String s) {
      int l = 0, r = 0;
      char[] arr = s.toCharArray();
      for(char c : arr){  // Check the minimum ( and ) to delete.
          if(c != '(' && c != ')')  continue;
          if(c == '(') l++;
          else{
              if(l <= 0) r++;
              else l--;
          }
      }
      List<String> result = new LinkedList<>();
      dfs(s, l, r, 0, result);
      if(result.size() == 0) result.add("");
      return result;
       }
       private void dfs(String s, int l, int r, int index, List<String> result){
      if(l == 0 && r == 0 && isValid(s)) result.add(s);   //if no ( or ) to delete and current string is valid, we can add this string to result list.
      char[] arr = s.toCharArray();
      for(int i = index; i < s.length(); i++){
          // if we have continuous ( or ), we just need to remove this first one so we won't get any duplicate result.
          if((arr[i] != '(' && arr[i] != ')') || (i > 0 && arr[i - 1] == arr[i])) continue;
          // We first delete ) for pruning
          if(r > 0 && arr[i] == ')'){
              // if we remove right, we need to decrease r and renew the current index.
              dfs(s.substring(0, i) + s.substring(i + 1), l, r - 1, i, result);
          }else if(l > 0 && arr[i] == '('){
          // if we remove right, we need to decrease l and renew the current index.
              dfs(s.substring(0, i) + s.substring(i + 1), l - 1, r, i, result);
          }
      }
       }
       private boolean isValid(String s){
      int count = 0;
      char[] arr = s.toCharArray();
      for(char c : arr){
          if(c != '(' && c != ')')  continue;
          if(c == '(') count++;
          else{
              if(count > 0) count--;
              else return false;
          }
      }
      return true;
       }
     }
     

Second time

• Method 1
  • Need to make full use of pruning.
  • Add index variable to remove the number of iteration.
  • merge removing ( and ) together.

      class Solution {
      public List<String> removeInvalidParentheses(String s) {
          int left = 0, right = 0;
          char[] arr = s.toCharArray();
          for(int i = 0; i < arr.length; i++){
              if(arr[i] == '(' || arr[i] == ')'){
                  if(arr[i] == '(')   left ++;
                  else{
                      if(left > 0) left --;
                      else if(left == 0) right++;
                  }
              }
          }
          Set<String> set = new HashSet<>();
          dfs(s, set, left, right, 0);
          List<String> rr = new LinkedList<>();
          if(set.isEmpty()) rr.add("");
          else rr.addAll(set);
          return rr;
      }
      private void dfs(String s, Set<String> result, int left, int right, int index){
          char[] arr = s.toCharArray();
          if(left == 0 && right == 0 && valid(arr)){
              result.add(s);
              return;
          }
          for(int i = index; i < arr.length; i++){
              if(arr[i] != '(' && arr[i] != ')' || (i > 0 && arr[i - 1] == arr[i])) continue;
              if(right > 0 && arr[i] == ')')   dfs(s.substring(0, i) + s.substring(i + 1), result, left, right - 1, i);
              else if(left > 0 && arr[i] == '(') dfs(s.substring(0, i) + s.substring(i + 1), result, left - 1, right, i);
          }
      }
      private boolean valid(char[] arr){
          int count = 0;
          for(int i = 0; i < arr.length; i++){
              if(arr[i] == '(' || arr[i] == ')'){
                  if(arr[i] == '(') count++;
                  else count --;
                  if(count < 0) return false;
              }
          }
          return count == 0;
      }
      }
    

Reference

1. 花花酱 LeetCode 301. Remove Invalid Parentheses - 刷题找工作 EP139