0921-使括号有效的最少添加

Raphael Liu Lv10

只有满足下面几点之一,括号字符串才是有效的:

  • 它是一个空字符串,或者
  • 它可以被写成 ABAB 连接), 其中 AB 都是有效字符串,或者
  • 它可以被写作 (A),其中 A 是有效字符串。

给定一个括号字符串 s ,在每一次操作中,你都可以在字符串的任何位置插入一个括号

  • 例如,如果 s = "()))" ,你可以插入一个开始括号为 "(()))" 或结束括号为 "())))"

返回 _为使结果字符串s 有效而必须添加的最少括号数_。

示例 1:

**输入:** s = "())"
**输出:** 1

示例 2:

**输入:** s = "((("
**输出:** 3

提示:

  • 1 <= s.length <= 1000
  • s 只包含 '('')' 字符。

方法一:贪心

这道题是括号匹配的题目。每个左括号必须对应一个右括号,而且左括号必须在对应的右括号之前。

对于括号匹配的题目,常用的做法是使用栈进行匹配,栈具有后进先出的特点,因此可以保证右括号和最近的左括号进行匹配。其实,这道题可以使用计数代替栈,进行匹配时每次都取距离当前位置最近的括号,就可以确保平衡。

从左到右遍历字符串,在遍历过程中维护左括号的个数以及添加次数。

如果遇到左括号,则将左括号的个数加 1。

如果遇到右括号,则需要和前面的左括号进行匹配,具体做法如下:

  • 如果左括号的个数大于 0,则前面有左括号可以匹配,因此将左括号的个数减 1,表示有一个左括号和当前右括号匹配;

  • 如果左括号的个数等于 0,则前面没有左括号可以匹配,需要添加一个左括号才能匹配,因此将添加次数加 1。

遍历结束后,需要检查左括号的个数是否为 0。如果不为 0,则说明还有剩下的左括号没有匹配,对于每个剩下的左括号都需要添加一个右括号才能匹配,此时需要添加的右括号个数为剩下的左括号个数,将需要添加的右括号个数加到添加次数。

无论是哪种添加的情况,都是在遇到括号无法进行匹配的情况下才进行添加,因此上述做法得到的添加次数是最少的。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def minAddToMakeValid(self, s: str) -> int:
ans = cnt = 0
for c in s:
if c == '(':
cnt += 1
elif cnt > 0:
cnt -= 1
else:
ans += 1
return ans + cnt
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int minAddToMakeValid(String s) {
int ans = 0;
int leftCount = 0;
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (c == '(') {
leftCount++;
} else {
if (leftCount > 0) {
leftCount--;
} else {
ans++;
}
}
}
ans += leftCount;
return ans;
}
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
public int MinAddToMakeValid(string s) {
int ans = 0;
int leftCount = 0;
int length = s.Length;
for (int i = 0; i < length; i++) {
char c = s[i];
if (c == '(') {
leftCount++;
} else {
if (leftCount > 0) {
leftCount--;
} else {
ans++;
}
}
}
ans += leftCount;
return ans;
}
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int minAddToMakeValid(string s) {
int ans = 0;
int leftCount = 0;
for (auto &c : s) {
if (c == '(') {
leftCount++;
} else {
if (leftCount > 0) {
leftCount--;
} else {
ans++;
}
}
}
ans += leftCount;
return ans;
}
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int minAddToMakeValid(char * s){
int ans = 0;
int leftCount = 0;
int length = strlen(s);
for (int i = 0; i < length; i++) {
char c = s[i];
if (c == '(') {
leftCount++;
} else {
if (leftCount > 0) {
leftCount--;
} else {
ans++;
}
}
}
ans += leftCount;
return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var minAddToMakeValid = function(s) {
let ans = 0;
let leftCount = 0;
let length = s.length;
for (let i = 0; i < length; i++) {
const c = s[i];
if (c === '(') {
leftCount++;
} else {
if (leftCount > 0) {
leftCount--;
} else {
ans++;
}
}
}
ans += leftCount;
return ans;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
func minAddToMakeValid(s string) (ans int) {
cnt := 0
for _, c := range s {
if c == '(' {
cnt++
} else if cnt > 0 {
cnt--
} else {
ans++
}
}
return ans + cnt
}

复杂度分析

  • 时间复杂度:O(n),其中 n 是字符串的长度。遍历字符串一次。

  • 空间复杂度:O(1)。只需要维护常量的额外空间。

 Comments
On this page
0921-使括号有效的最少添加