小知识,大挑战!本文正在参与“程序员必备小知识”创作活动。
题目描述
给你一个由若干括号和字母组成的字符串
s
,删除最小数量的无效括号,使得输入的字符串有效。返回所有可能的结果。答案可以按 任意顺序 返回。
示例1 :
输入:s = "()())()"
输出:["(())()","()()()"]
复制代码
示例2 :
输入:s = "(a)())()"
输出:["(a())()","(a)()()"]
复制代码
示例3 :
输入:s = ")("
输出:[""]
复制代码
思路:DFS+剪枝
- 从左向右遍历字符串,只要出现右括号比左括号多的情况,可以删除前面任意一个右括号,进入下次递归。
- 如果一直不出现右括号比左括号多的情况,说明右括号已经删除完毕,这时可能有多余的左括号
- 从右向左遍历字符串,删除可能的多余左括号,与删除右括号逻辑一致
class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> result = new ArrayList<>();
if (s.equals("()") || s.equals("")) {
result.add(s);
return result;
}
Deque<String> queue = new ArrayDeque<>();
queue.offer(s);
HashSet<String> set = new HashSet<>(); //用于存储裁剪后的元素,防止重复元素加入队列
boolean isFound = false; //判断是否找到了有效字符串
while (!queue.isEmpty()) { //队列不为空
for(String cur:queue){
if (isValid(cur)) {
result.add(cur);
isFound = true;
}
}
if (isFound) { //找到后不再进行裁剪
break;
}
//裁剪过
Deque<String> queue2 = new ArrayDeque<>();
for( String curr:queue) {
for (int i = 0; i < curr.length(); i++) {
if (curr.charAt(i) == '(' || curr.charAt(i) == ')') { //只对'('或')'进行裁剪
String str;
if (i == curr.length() - 1) {
str = curr.substring(0, curr.length() - 1);
} else {
str = curr.substring(0, i) + curr.substring(i + 1);
}
if (set.add(str)) { //如果集合中还未有该字符串
queue2.offer(str);
}
}
}
}
queue = queue2;
}
if (result.isEmpty()) {
result.add("");
}
return result;
}
private static boolean isValid(String s) {
int left = 0;
for (int i = 0; i < s.length(); i++) {
int curr = s.charAt(i);
if (curr == '(') {
left++;
} else if (curr == ')') {
if (left != 0) {
left--;
} else {
return false;
}
}
}
return left == 0;
}
}
复制代码
近期评论