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())()"]
")(" -> [""] 首先，遍历所有情况，然后看是否最后得到的string是否满足所有valid parentheses的情况，满足的话，就比较已经存在的valid parentheses. 否则就放弃。
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<String>();
int[] max = { };
dfs(s, "", , res, max);
if (res.size() == ) {
res.add("");
}
return res;
}
private void dfs(String str, String subRes, int countLeft, List<String> res, int[] max) {
if (countLeft > str.length()) return;
if (str.length() == ) {
if (countLeft == && subRes.length() != ) {
if (subRes.length() > max[]) {
max[] = subRes.length();
res.clear();
}
if (max[] == subRes.length() && !res.contains(subRes)) {
res.add(subRes.toString());
}
}
return;
}
if (str.charAt() == '(') {
dfs(str.substring(), subRes + "(", countLeft + , res, max);
dfs(str.substring(), subRes, countLeft, res, max);
} else if (str.charAt() == ')') {
if (countLeft > ) {
dfs(str.substring(), subRes + ")", countLeft - , res, max);
}
dfs(str.substring(), subRes, countLeft, res, max);
} else {
dfs(str.substring(), subRes + str.charAt(), countLeft, res, max);
}
}
}
重写了一遍，思路有点不一样。
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> list = new ArrayList<>();
if (s == null) return list;
list.add("");
helper(s, , "", , list);
return list;
}
void helper(String str, int index, String tempString, int leftCount, List<String> list) {
if (str.length() < || index > str.length()) return;
// if the number of "(" is greater than the remaining number of letters in the string, we should return
// ex: "((((", but in the str, the remaining letters are less than leftCount
if (leftCount > str.length() - index) return;
// if the length(remaining letters + tempString) < length(exist strings) in the list
// ex: str = "(((()))" index = 6 tempString = "(" list : "(())"
if (list.size() != && list.get().length() > tempString.length() + str.length() - index) return;
// reached the end of the original string
if (index == str.length() && leftCount == ) {
if (list.get().length() < tempString.length()) {
list.clear();
list.add(tempString);
} else if (list.get().length() == tempString.length() && !list.contains(tempString)) {
list.add(tempString);
}
return;
}
// add the current letter to the tempString or not
if (str.charAt(index) == '(') {
helper(str, index + , tempString + "(", leftCount + , list); // add
helper(str, index + , tempString, leftCount, list); // does not add
} else if (str.charAt(index) == ')') {
if (leftCount != ) {
helper(str, index + , tempString + ")", leftCount - , list); // add
}
helper(str, index + , tempString, leftCount, list); // does not add
} else { // has special letters
helper(str, index + , tempString + str.charAt(index), leftCount, list); // add
}
}
}