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: [""]
- This question can use dfs to solve, and this question can be divided into 2 parts:
- Find the minimun '(' number and ')' number to delete.
- 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;
}
}- 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; } }
- Method 1: dfs
class Solution { private: pair<int, int> checkParentheses(string s){ const int n = s.length(); int l = 0, r = 0; for(int i = 0; i < n; ++i){ if(isalpha(s[i])) continue; else if(s[i] == '(') l++; else{ if(l <= 0) r++; else l--; } } pair<int, int> p(l, r); return p; } vector<string> res_; bool valid(string s){ int l = 0, r = 0; for(const char& c : s){ if(c == '(') l++; else if(c == ')'){ if(++r > l) return false; } } return l == r; } void dfs(int l, int r, string s, int index){ if(l == 0 && r == 0 && valid(s)) res_.emplace_back(s); for(int i = index; i < s.length(); ++i){ if(isalpha(s[i]) || (i > 0 && s[i] == s[i - 1])) continue; if(r > 0 && s[i] == ')'){ dfs(l, r - 1, s.substr(0, i) + s.substr(i + 1), i); }else if(l > 0 && s[i] == '('){ dfs(l - 1, r, s.substr(0, i) + s.substr(i + 1), i); } } } public: vector<string> removeInvalidParentheses(string s) { pair<int, int> p = checkParentheses(s); dfs(p.first, p.second, s, 0); return res_; } };