第六章 - 高频考题(困难)
0301. 删除无效的括号

题目地址(301. 删除无效的括号)

题目描述

1
删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。
2
3
说明: 输入可能包含了除 ( 和 ) 以外的字符。
4
5
示例 1:
6
7
输入: "()())()"
8
输出: ["()()()", "(())()"]
9
示例 2:
10
11
输入: "(a)())()"
12
输出: ["(a)()()", "(a())()"]
13
示例 3:
14
15
输入: ")("
16
输出: [""]
Copied!

前置知识

  • BFS
  • 队列

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

我们的思路是先写一个函数用来判断给定字符串是否是有效的。 然后再写一个函数,这个函数 依次删除第i个字符,判断是否有效,有效则添加进最终的返回数组。
这样的话实现的功能就是, 删除一个 小括号使之有效的所有可能。因此只需要递归调用依次删除第i个字符的功能就可以了。
而且由于题目要求是要删除最少的小括号,因此我们的思路是使用广度优先遍历,而不是深度有限的遍历。
301.remove-invalid-parentheses
没有动图,请脑补

关键点解析

  • 广度优先遍历
  • 使用队列简化操作
  • 使用一个visited的mapper, 来避免遍历同样的字符串

代码

1
var isValid = function(s) {
2
let openParenthes = 0;
3
for(let i = 0; i < s.length; i++) {
4
if (s[i] === '(') {
5
openParenthes++;
6
} else if (s[i] === ')') {
7
if (openParenthes === 0) return false;
8
openParenthes--;
9
}
10
}
11
return openParenthes === 0;
12
};
13
/**
14
* @param {string} s
15
* @return {string[]}
16
*/
17
var removeInvalidParentheses = function(s) {
18
if (!s || s.length === 0) return [""];
19
const ret = [];
20
const queue = [s];
21
const visited = {};
22
let current = null;
23
let removedParentheses = 0; // 只记录最小改动
24
25
while ((current = queue.shift())) {
26
let hit = isValid(current);
27
if (hit) {
28
if (!removedParentheses) {
29
removedParentheses = s.length - current.length
30
}
31
if (s.length - current.length > removedParentheses) return ret.length === 0 ? [""] : ret;;
32
ret.unshift(current);
33
continue;
34
}
35
for (let i = 0; i < current.length; i++) {
36
if (current[i] !== ')' && current[i] !== '(') continue;
37
const subString = current.slice(0, i).concat(current.slice(i + 1));
38
if (visited[subString]) continue;
39
visited[subString] = true;
40
queue.push(subString);
41
}
42
}
43
44
return ret.length === 0 ? [""] : ret;
45
};
Copied!

扩展

相似问题: